Sudoku

A Sudoku is a grid puzzle, like a crossword, but with numbers instead of letters.    It's usually a 9 by 9 grid of 81 cells, partitioned  into nine, 3 by 3 boxes like the pictures below.

How the automatic Sukoku solver works

There is an automatic Sudoku solver on my website.  In a partially-complete Sudoku the blank cells can only take values not already contained in the same row, column or box.

So whenever you write a number into a cell you further restrict the permitted values for lots of other squares.

When you come to an impasse it's because there's an unfilled cell with no permitted values left.  Such a cell is blocked.

When you find a blocked cell  you have to backtrack to some earlier stage and try alternatives, which is time consuming.

Therefore a good strategy is to put lots of effort into avoiding blocking cells.

Fortunately it's easy to spot when a cell is likely to become blocked.   Any cell with very few permitted remaining values is in the greatest danger of being blocked.  Therefore a good strategy is to fill such cells first, while it's still possible.

That's what the automatic solver does.  At each step it works out  all permitted entries for every blank cell.  Firstly it fills those blanks which have only one permitted entry, recalculating permitted entries between such fillings.  Then it moves onto cells with two or more permitted entries.  It randomly picks one in the greatest danger of becoming blocked (one that has a small number  of posible values left) and inserts a randomly chosen permitted value.  It keeps repeating this process till either it succeeds or it reaches an impasse, whereupon it backtracks.   However, because of the way it tries to avoid blocked cells, backtracking is minimised.

The devil, of course is in the detail.

Facts About Sudokus

The name Sudoku is a trademark of the Japanses publisher Nikoli and is an abbreviation of the Japanese phrase (roughly) suuji wa dokushin ni kagiru, ("digits must remain single").

There is nothing special about using numbers in the grids.  Any set of nine distinct symbols are just as good.  Many people use letters instead.

There are actually 6,670,903,752,021,072,936,960 (= about 6.67x10²¹ =  2²⁰x3⁸x5x7x27,704,267,971) distinct Sudokus, i.e. sets of 9x9 grids which satisfy the Sudoku rules.   Since re-labelling the symbols converts one valid Sudoku into another, and since there are 362,880 different permutations of 9 symbols, we can divide the number of distinct Sudokus by  this number giving 18,383,222,420,692,992 Sudokus, no two of which are symbol-permutations of each other.

We can take this idea further and note that any of the following converts one valid Sudoku  into another.

• Relabelling entries
• Reflection
• Rotation
• Permutation of blocks of columns 1-3, 4-6 and 7-9
• Permutation of blocks of rows 1-3, 4-6 and 7-9
• Permutation of columns 1-3
• Permutation of rows 1-3
• Permutation of columns 4-6
• Permutation of rows 4-6
• Permutation of columns 7-9
• Permutation of rows 7-9

When we take all these variants into account there are still  5472730538 (=2x11²x23x983,243) essentially different Sudoku grids which cannot be inter-converted by using  any of the above manoevres.

For perhaps more information than you can cope with see this entry in  Wikipedia.

If you want the working parts of a solver for your own website contact me.