Monday, May 9, 2016

Sudoku Math Puzzles

Sudoku (originally called Number Place) is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution.

Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same row, column or in any of the nine 3×3 subregions of the 9x9 playing board.

                                                   Sudoku puzzle (black) solved (in red)

French newspapers featured variations of the puzzles in the 19th century, and the puzzle has appeared since 1979 in puzzle books under the name Number Place.  However, the modern Sudoku only started to become mainstream in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It first appeared in a US newspaper and then The Times (UK) in 2004, from the efforts of Wayne Gould, who devised a computer program to rapidly produce distinct puzzles.

The modern Sudoku was most likely designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor from Connersville, 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. He died in 1989 before getting a chance to see his creation as a worldwide phenomenon.

Mathematics of Sukoku

The results in the following text refer to classic Sudoku, disregarding jigsaw, hyper and others.

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 7021666999999999999♠6.67×1021. This is roughly 6994120000000000000♠1.2×10−6 times the number of 9×9 Latin squares. Various other grid sizes have also been enumerated. 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).

No comments:

Post a Comment