If you want puzzles to solve, try visiting Gaby van Hegan's puzzle pages (now hosted by playr.co.uk), Times on-line or SuDoku.com. If you want really hard puzzles to solve, try Wei-Hwa Huang's blog.
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
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.
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 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.
For those interested in the gory details, this page's solver only
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
guess and back-track from what they commonly call
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
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: