Su Doku puzzle solver

If you want puzzles to solve, try visiting SuDoku.com (Gaby van Hegan's used to have some, but the link broke; and Wei-Hwa Huang's blog used to have really hard ones).

Since your user agent is currently (perhaps even prudently) ignoring scripting, you can't use my experimental Su Doku puzzle helper. If you have the option of turning on JavaScript (or ECMAScript, as it's officially called), doing so (and probably re-loading) should change that; otherwise, you can always follow a link above or use the Back button on your user agent.

First input (only) the entries supplied by whoever set the puzzle; then hit return to freeze those as givens; the solver shall then work out what it can, using the simple rules described below. After that, the entries you type in shall be displayed differently and you'll be able to undo the most recent of them by typing back-space, regardless of where keyboard focus is. You should get tool-tips indicating which values are still possible for a cell, if you hover it; and you should only be able to input a value for a cell if it's blank. YMMV: this is experimental software.

Time-reversed record of actions. Rows and columns are numbered from 0 at top and left to 8 at bottom and right; central row and column are numbered 4. A cell is referred to as (x, y), where x is the number of columns to the left of it and y is the number of rows above it.

For anyone unfamiliar with the puzzle, the rules are very simple: each row and each column should contain each of the digits from 1 to 9 exactly once, as should each of the nine 3×3 tiles obtained by splitting the grid's height and width up into thirds. The puzzle, as set, supplies some cells with values and you are to fill in the remaining cells so as to satisfy these constraints.

Why bother ?

Most of the fun of a game of Su Doku is in doing it yourself: so a solver is a bit pointless – especially as even a very dumb one can solve problems that we get to enjoy solving by using intelligence rather than (as the program does) memory. We have trouble holding even a dozen distinct fragments of information in our heads all at one go, where the computer finds 729 (for each of 81 cells, which of 9 entries might be present there) easy.

None the less, a solver isn't entirely without its uses. If it explains the steps of its reasoning, you can read those and it may help you learn techniques for solving Su Doku puzzles quicker for yourself. The approach I've taken is to have the program only do the steps that require no look-ahead – it does what it can, then leaves you to chose a cell to experiment in. If that leads to an error, it backs out of the experiment and learns that that cell can't take the value you tried in it. This makes it easier to follow what it did and why.

I've mainly found this solver useful

when I get stuck on a puzzle, to check I've not missed any forward inferences; I look at the shape of which bits it has / not filled in (rather than what answers it's put there) and try to work out how it knew answers to the bits I missed; and
after I've finished solving it, to see if there's a single cell I can fill in wrong for which the solver shall discover that this is wrong and then complete the puzzle without further help.

It was a long time before I found a puzzle for which there is no such single cell (it was playr.co.uk's Fiendish puzzle of the day for 2006/July/13th; there are four cells of it which, if filled in correctly lead it to the answer). Checking for inferences I've missed, and reading the solver's rather cryptic account of its reasoning, have helped me to be more thorough about finding all the things forward inference can reveal.

What does it do ?

For those interested in the gory details, this page's solver only does forward reasoning, until the user intervenes. Exploring an option and eliminating it if it leads to error is formally equivalent to the logical process called reductio ad absurdum. Even before Kurt Gödel gave us all some reasons to mistrust reductio, there was a school of mathematicians – the constructivists – which rejected its use, at the expense of having to approach assorted topics – notably continuity – in unorthodox ways. The fact that many Su Doku enthusiasts distinguish guess and back-track from what they commonly call pure logic could be construed as a groundswell of constructivist sympathy.

The actual pieces of forward reasoning in use here are:

Each cell remembers which values it might potentially hold; if there are none, it tells the grid it's in error; when there's only one left, the cell's value becomes definitely that;
When a cell's value becomes definite, it tells all those in its row, column and tile that they can't have that value; if any of them object to this (because it's also their only candidate digit), the cell tells the grid it's in error;
Each row, column and 3×3 tile will notice if it only has one candidate for some given digit, and make that candidate be definitely that; if it has no candidate for a digit, it tells the grid it's in error;
Each row and column notices when all its candidates for some digit lie in the same tile, and tells the other cells of that tile that they can't be that digit;
Each tile notices when all its candidates for some digit are in the same row or column; and tells the other cells of that row or column that they can't be that digit;
When a grid, pushed onto the stack to explore the user's guess of a given digit in a given cell, is in error, it pops itself off the stack, restoring control to the prior grid and telling that grid that the given user input is not a valid entry for the given cell.
If there is some subset of the cells in a given row, column or tile which has at least as many members as the union of those cells' sets of possible digits (regardless of any other cells into which those digits think they can fall), then indeed those digits fall within those cells, and don't fall in any other cell of the given row, column or tile;
Conversely, if some subset of the digits has at most as many members as the set, within some row, column or tile, of cells in which any of those digits can fall (regardless of any other digits that might think they can fall in these cells), then those cells do indeed contain only those digits.

The last two check for partition, by cell and by number respectively. In either, if the at most or at least is not in fact equality, the grid is in error; they are just generalisations of the if a cell has only one candidate digit and if only one cell in a row, column or tile is a candidate for some digit rules above. Furthermore, if either partition rule applies, so does the other: given a partition by cell, the complement of the set of digits that can appear in its subset of cells will imply a partition by digit; and conversely. Thus implementing either partition rule systematically suffices to make the other work; I actually implement the former. Partitions do sometimes imply shorter lists of possible contents for some cells (as shown by tool-tips) than the solver used to find without them, but it wasn't until I was doing fiendish puzzles every day that I saw a puzzle (I recorded its ID as 5-533228 at the time, but attempts to find by that ID get a puzzle with no ID that's trivial to solve) in which they yielded a definite value for a cell that the solver didn't find using its simple rules.

There are some more complex rules, that would be harder to implement so I deferred doing so until the above all worked smoothly. I might eventually get round to encoding:

If, in two tiles of a row (column) of tiles, a given digit is limited to (at most) two of the rows (columns) the tiles share, then the third tile must have that digit in the third shared row (column);

Written by Eddy.