A completed Sudoku grid is a special type of Latin square with the additional property of no repeated values in any 3×3 block. The relationship between the two theories is now completely known, after Denis Berthier has proven in his recent book, "The Hidden Logic of Sudoku"[17], 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.
The number of classic 9×9 Sudoku solution grids was shown in 2005 by Bertram Felgenhauer and Frazer Jarvis to be 6,670,903,752,021,072,936,960[18] (sequence A107739 in OEIS) : this is roughly 0.00012% 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 and relabelling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538[19] (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,[20][21] and 18 with the givens in rotationally symmetric cells
Number puzzles first appeared in newspapers in the late 19th century[citation needed], when French puzzle setters began experimenting with removing numbers from magic squares. Le Siècle, a Paris-based daily, published a partially completed 9×9 magic square with 3×3 sub-squares in 1892.[22] It was not a Sudoku because it contained double-digit numbers and required arithmetic rather than logic to solve, but it shared key characteristics: each row, column and sub-square added up to the same number.
Within three years Le Siècle's rival, La France, refined the puzzle so that it was almost a modern Sudoku. It simplified the 9×9 magic square puzzle so that each row and column contained only the numbers 1–9, but did not mark the sub-squares. Although they are unmarked, each 3×3 sub-square does indeed comprise the numbers 1–9. However, the puzzle cannot be considered the first Sudoku because, under modern rules, it has two solutions. The puzzle setter ensured a unique solution by requiring 1–9 to appear in both diagonals.
These weekly puzzles were a feature of newspaper titles including L'Echo de Paris for about a decade but disappeared about the time of the First World War.[23]
According to Will Shortz, the modern Sudoku was most likely designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor from Indiana, and first published in 1979 by Dell Magazines as Number Place (the earliest known examples of modern Sudoku). Garns's name was always present on the list of contributors in issues of Dell Pencil Puzzles and Word Games that included Number Place, and was always absent from issues that did not.[11] He died in 1989 before getting a chance to see his creation as a worldwide phenomenon.[11] It is unclear if Garns was familiar with any of the French newspapers listed above.
The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984[11] as Suuji wa dokushin ni kagiru (数字は独身に限る, Suuji wa dokushin ni kagiru?), which can be translated as "the digits must be single" or "the digits are limited to one occurrence." At a later date, the name was abbreviated to Sudoku by Maki Kaji (鍜治 真起, Kaji Maki?), taking only the first kanji of compound words to form a shorter version.[11] In 1986, Nikoli introduced two innovations: the number of givens was restricted to no more than 32, and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells).[10] It is now published in mainstream Japanese periodicals
see also---
List of Sudoku terms and jargon
Killer sudoku
Sudokube (3D variant)
Latin square
Logic puzzle
List of Nikoli puzzle types
Kakuro
Nonogram (aka Paint by numbers, O'ekaki)
No comments:
Post a Comment