Starting with Sudoku

I’ve had an idea for a while to use Sudoku as a playground to explore Computer Science™. And what better way to start than by documenting a quick crappy implementation of a Sudoku solver?

tl;dr

Here’s a thrown-together version. Click solve, and it will iterate until there are no more changes. It doesn’t actually understand that it’s solved the puzzle, it just gives up because it can’t find any more “moves” to make.

Basic Structure

The code is split into 3 parts:

1. The Game, stored as a single flat list of cells. A cell is a value and a list of potential values. The value is the number that you’d write into a pen-and-paper Sudoku game. The list of potential values is the numbers that the solver has decided could go into this cell, based on what it’s figured out so far.

   Each cell starts with a potential list of 1 through 9, since we start off green-field!

2. The viewer. This is basically just a bunch of React views that put together a HTML table of either a cell’s value or all of the potential values.

3. The solver. In my initial garbage version, if you squint, you can make out 3 parts:

   Functions that examine a structure to either eliminate (reduce), or infer possible values based on other row/column/block values and possible values;

   Transformers that rearrange the list of cells to make reduction/inference simpler;

   And the harness that iterates through the reduction/inference functions until it notices that no progress has been made.

For the rest of this excursion, I’m going to focus on the solver functions, with a bit of dabbling in the game structure.

Solving

We have two basic operations, reducing the possibilities, and inferring values. We can do both actions on rows, columns and blocks – by block I’m referring to the 3x3 subsets of the puzzle – resulting in 6 possible actions.

The structure of the game is a single list, where each set of 9 numbers represents a row, and we can mark unfilled cells with null, so in a reduced 3x3 puzzle [null, 3, null, 4, null, 5, null, null, 2] would represent:

So to do actions, we extract rows, columns or blocks, and then reduce or infer…

Reduction

How do we reduce a row? First, we need to extract rows out of the list. We just group the items in sets of 3 in this example, 9 in the real puzzle.

Once we have the row data, reduction is simply collecting the values of each cell in the row:

values = block.map(function(cell) {
     return cell.value;
}).filter(function(val) { return !!val });

then removing these values from the possible values of all other cells (with a short-circuit for when the cell already has a value):

return block.map(function(cell) {
    var possible = !!cell.value ? [] : cell.possible.filter(function(val) { return values.indexOf(val) == -1  });
    return {
       value: cell.value,
       possible: possible
    };
});

With a row of

We can see that the values in the row are {1,7,3}. None of the cells in this row can have 1, 3 or 7 in their set of possible values, so we can remove them from the possible list of values of each cell.

Considering values and possible values separately like this makes it simpler, as we don’t have to remember which cell holds which value.

Reducing every row is simply repeating the above process across each row.

reduceColumns()

Naively, we could implement reduceColumns() by collecting every 9th element of the list, then performing a similar action to reduceRow() above. But consider that if we transpose the whole puzzle, rows become columns, and columns become rows!

And we already know how to, er, reduceRows()… So given reduceRows() and transpose() we can trivially implement reduceColumns() as transpose(reduceRows(transpose(game))).

reduceBlocks()

I puzzled on this for a while, trying to come up with a smart-ass golf shot to implement this in the same vein as column reduction, and stared at this for a while:

Somehow, I came up with this:

function toRows(blocks, blockLength, rowLength) {
     var blockRows = inGroupsOf(blocks, blockLength * rowLength);
     linearRows = blockRows.map(function(blockRow) {
       return flatten(transpose(inGroupsOf(inGroupsOf(inGroupsOf(blockRow, blockLength), rowLength)[0], blockLength)));
     });
     return flatten(linearRows);
}

and I have no idea how this actually works, even only a few days after writing it. I’m going to hand-wave and leave the explanation to another article, but suffice it to say, this works and it’s reversible! It effectively acts as transpose() for swapping between blocks and rows. Given this, reduceBlocks() is trivially the same as reduceColumns(): toRows(reduceRows(toRows(game))).

“Inference”

The inference step is more involved than reduction. Here’s the code for it, we’ll break it down in a moment:

function infer(rows) {
     var newRows = rows.map(function(row) {
     return row.map(function(cell) {
        var newCell = {
           value: cell.value,
           possible: cell.possible
        }
        if (!!cell.value) return newCell;
     
        var onlyHere = cell.possible.reduce(function(memo, val) {
          if (row.every(function(otherCell) {
              return (otherCell.value != val && otherCell.possible.indexOf(val) == -1) || otherCell === cell
            })) {
            memo.push(val);
          }
          return memo;
        }, []);

        if (onlyHere.length > 1) {
           // do something about it.
        } else if (onlyHere.length == 1) {
           return {
             value: onlyHere[0],
             possible: []
           }
        } else {
           return newCell;
        }
     });
    });
    return newRows;
}

Ignoring the woeful current state of the implementation, what this function does for each row/column/block is…

Duplicate the cell:

var newCell = {
   value: cell.value,
   possible: cell.possible
}

… Give up immediately if the cell already has a value (since there’s no point inferring anything):

if (!!cell.value) return newCell;

… Determine which of the possible values for this cell are only possible in this cell (when comparing with the rest of the row/column/block):

var onlyHere = cell.possible.reduce(function(memo, val) {
  if (row.every(function(otherCell) {
      return (otherCell.value != val && otherCell.possible.indexOf(val) == -1) || otherCell === cell
    })) {
    memo.push(val);
  }
  return memo;
}, []);

… Then, if there’s a value that can only be in this cell, go with it!

if (onlyHere.length > 1) {
   // do something about it.
} else if (onlyHere.length == 1) {
   return {
     value: onlyHere[0],
     possible: []
   }
} else {
   return newCell;
}

To visualise the core of the action, lets start with the following row from the demonstration puzzle. After a few rounds of working, we have (small numbers are potential values):

Let’s examine cell 2, second from left. It has two potential values, 2 and 7. 2 can be in cells 3, 7 and 8; but 7 can only be in cell 2. Therefore, cell 2 must be 7:

Using the same transforms as we used for reduction, we can do this inference for columns and blocks too.

Holding It All Together with Duct Tape and String.

Given the actions above, and a way to compare the world after each step, we can simply iterate through our actions

1. Reduce rows
2. Reduce columns
3. Reduce blocks
4. Infer rows
5. Infer columns
6. Infer blocks

until we notice that there has been no change for a complete cycle. We can’t stop after the first action that does nothing, as it’s possible that we need to infer values for a row, before we can reduce values in a column.

In my implementation, detecting lack of change is simple because, for visualisation purposes, I keep track of what possiblities are removed by each action. This visualisation is disabled in the version linked to above though, as it just attempts to solve the puzzle in one run of the Javascript event loop.

What’s Missing?

For some puzzles, the inference and reduction steps are not enough to find a solution. We’d get stuck before arriving at a solution, and need to pick an arbitrary unfilled cell, make a guess at a value, and then verify if this results in a solution. One way of doing this is implementing a tree search, where each possible value for a cell represents a child node to explore.