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 level-headed 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 pre-computed all the board position indices that the algorithm uses.