Su Doku puzzle solver

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

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.

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

It was a long time before I found a puzzle for which there is no such single cell (it was'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:

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:

Valid CSSValid HTML 4.01 Written by Eddy.