Sudoku

How to solve it algorithmically? We can represent the set of possible values for each cell, starting with {1-9} for each blank cell and {n} for a cell specified as holding the number n.

Within each nonet we then reduce the cardinality of the sets in the blank cells until the cardinality reaches 1, in which case we have the answer.

Two reduction strategies, one based on identifying identical cells and one based on identifying a cell whose set is the only one to hold a particular number.

The identification of a group of identical cells can be done by sorting. Where the number of such cells is equal to the cardinality of the set that is the cell value, the numbers must be arranged among these cells and cannot be anywhere else in the nonet. So we can eliminate the elements of this chosen set from all other cells in the nonet.

Where we can identify a number that is a candidate in only one cell, we know that that call must contain that number. We can extend this to the identification of two numbers that are each candidates in the same two cells, and then eliminate all other candidates from these two cells. This actually works in general for more numbers, but gets very labour intensive.

How many possible solution grids exist?

6,670,903,752,021,072,936,960
according to New Scientist 24/31 December 2005.

There are 9 possible choices for the top LH cell, 8 for the one to its right, etc. There are then 8 possible choices for the LH call in the second row, etc

9	8	7	6	5	4	3	2	1
8	7	6
7	6	5

Note: The numbers in the cells are the number of possible choices for filling in the cell, on the assumption that all the cells in earlier rows have been filled, and also the cells to its left on the same row.

However, as this continues: the suggestion that there are 5 choices for the red cell assumes that none of the three numbers above it is the same as the number to its left.

The 7 grey cells are also under-estimates for similar reasons.

9	8	7	6	5	4	3	2	1
6	5	4	6	5	4	6	5	4
3	2	1	3	2	1	3	2	1
6	5	4
3	2	1
3	2	1

Each cell is a member of 3 nonets, a row, a column and a 3x3 square.
The row and column intersect at only the cell under consideration, but each intersects with the 3x3 square in 2 other cells. e.g. for the red square, the column intersects in the 2 grey squares immediately beneath it, and the row intersects in the green and grey squares either side of the red one.

Consider filling cell-by-cell. The number of digits available for the chosen cell depends on the other numbers already inserted in the three intersectin nonets.

Let n_r, n_c, n_s be the number of digits already filled in the row, column and 3x3 square respectively.
We need to consider separately the different cases according to how many digits are duplicated between the 3 different intersecting nonets.
Let d be the number of duplicate digits.
Let N be the number of arrangements before filling in our chosen square.
an_d N_d the number of such arrangements in which d digits are duplicated among the 3 nonets.
N =
Σ
d N_d

The number of choices of digit for the chosen cell is
9 - n_r - n_c - n_s - d or 0 if this number is negative

The number of choices after filling in the chosen cell is:
N ' =
Σ
d N_d ( 9 - n_r - n_c - n_s - d )

where the sum is taken of those values of d for which the bracket is positive.

Let n_d be the number of ways in which the 3 nonets can be configured with d digits duplicated.
This just by changing the digits in the n_r, n_c, n_s cells that are treated as occupied at this stage.
The total number of such arrangements is
n =
Σ
d n_d

So we can divide up N :
N_d = n_d
n N

So we start with 9 choices for the first square, and then repeat the above calculation for each of the 80 others. The only slightly tricky bit is to evaluate the values of n_d at each stage.