Sudoku - Mathematics of Sudoku

Mathematics of Sudoku

A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any of the 9 blocks of contiguous 3×3 cells. The relationship between the two theories is now completely known, after it was proven that a first-order formula that does not mention blocks (also called boxes or regions) is valid for Sudoku if and only if it is valid for Latin Squares (this property is trivially true for the axioms and it can be extended to any formula).

The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately 6.67×1021. This is roughly 1.2×10−6 times the number of 9×9 Latin squares. Various other grid sizes have also been enumerated—see the main article for details. The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538 (sequence A109741 in OEIS).

The maximum number of givens provided while still not rendering a unique solution is four short of a full grid (77); if two instances of two numbers each are missing from cells which occupy 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—was recently proven to be 17. A number of valid puzzles with 17 givens have been found for the standard variation without a symmetry constraint, by Japanese puzzle enthusiasts, and 18 with the givens in rotationally symmetric cells. Over 48,000 examples of Sudoku puzzles with 17 givens resulting in a unique solution are known.

In 2010 mathematicians of the University of Southern California showed that the arrangement of numbers in Sudoku puzzles have greater Shannon entropy than the number arrangements in randomly generated 9×9 matrices. This is because the rules of Sudoku exclude some random arrangements that have an innate symmetry.