Sudoku Algorithm
|
The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete [1]. This gives some vague indication of why Sudoku is hard to solve, but on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
However, for a non-trivial starting board, the game tree is very large and so this method is not feasible. The problem of solving a puzzle that is known to have only one solution is in UP. Solving Sudoku puzzles can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. |
, where x and y are integers between 1 and 9. In this case, two
distinct vertices labelled by and 
are joined by an edge if and only if:
or,
or,
and 
A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960, which is roughly the number of micrometers to the nearest star. This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions. The number of valid Sudoku solution grids for the 16×16 derivation is not known.
The maximum number of givens that can be provided while still not rendering the solution unique, regardless of variation, is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be added. The inverse of this — the fewest givens that render a solution unique — is an unsolved problem, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts, and 18 with the givens in rotationally symmetric cells.
Printable Sudoku
Sudoku Rules
Sudoku Algorithm
Sudoku Strategy
Daily Sudoku
Sudoku History