Mathematics of Sudoku
The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete [8]. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
Solving Sudoku puzzles (as well as any other NP-hard problem) 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. The vertices can be labelled with the ordered pairs (x,\, y), where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by (x,\, y) and (x',\, y') are joined by an edge if and only if:
* x = x'\, or,
* y = y'\, or,
* \lceil x/3 \rceil = \lceil x'/3 \rceil and \lceil y/3 \rceil = \lceil y'/3 \rceil
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
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 [9] (sequence A107739 in OEIS). 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 [10] (sequence A109741 in OEIS). 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 is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy form the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be assigned. Since this applies to Latin squares in general, most variants of Sudoku have the same maximum. The inverse problem—the fewest givens that render a solution unique—is unsolved, 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 [11] [12], and 18 with the givens in rotationally symmetric cells.
Source:
Wikipedia.org
More:
A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles
click here for nine-page theory & foolproof system by American computer scientist James F. Crook.