A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any partition of the 9×9 block into contiguous 3×3 blocks. The relationship between the two theories is now completely known, after Denis Berthier proved in his recent book, "The Hidden Logic of Sudoku", 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).
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
More Sudoku
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The first known calculation of the number of classic 9×9 Sudoku solution grids was posted on the USENET newsgroup rec.puzzles in September 2003[11] and is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS). This is roughly 1.2×10−6 times the number of 9×9 Latin squares. A detailed calculation of this figure was provided by Bertram Felgenhauer and Frazer Jarvis in 2005.[12] 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 and relabelling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538[13] (sequence A109741 in OEIS).
The maximum number of givens provided while still not rendering a unique solution 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,[14][15] and 18 with the givens in rotationally symmetric cells. Over 47,000 examples of Sudokus with 17 givens resulting in a unique solution are known.
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
More Sudoku
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
No comments:
Post a Comment