
Sudoku Spolier: Technical stuff


Like with my "15 puzzle" applet, I didn't apply any standardized AI techniques. Nor did
I formulate this as a constraint programming problem. I merely figured out a way a
reasonably levelheaded person would solve it, and formalized it into an algorithm
that a computer could carry out. In short, this is how it works:
We examine all rows, columns and 3x3 square groups and check which numbers are missing.
For example, if we start with the top row, in the picture on the left, it lacks a
'2', '3', '7', '8' and '9'. Now, for each missing digit in the set of nine squares we are
currently looking at, check in which of the empty positions it can legally be placed.
Let's start with '2' and the top left square.
According to the rules, there can't be any duplicate digits in any
row, column or 3x3 group. So we have to check a related set of 20 squares (marked
with red in the picture on the right) and see if there is any other occurrence of
the digit '2'. Obviously, there is one in the first column, third row from the top.
So we can't put a '2' in the top left corner.
Applying the same analysis to the other four empty squares in the top row, we find
that there are two legal, possible positions in which we can put the '2' (marked with
green in the picture on the left). These are our best candidates for our next move
so far.
So we keep those in mind when we continue with the '3', '7', '8' and '9'. And then
the next row, and then all the columns and the 3x3 groups. If we happen to find a
missing digit with fewer legal positions, we discard our previously best
move candidates and keep the new ones instead.
Ideally, we would hope to find a digit, in some row, column or 3x3 group, which only
has one possible legal position. But in case we don't, that just means we have
to try each candidate in turn. The solution process will "branch out." And if we
encounter a missing digit that has no legal position, it means we have hit
a dead end and have to erase all our moves since the junction, and start a new branch
with the next candidate at that point.
In the program, this is all done by having the solution method recursively call itself
after each time it fills in a new square. And to speed things up I have precomputed all the
board position indices that the algorithm uses.

