# Sudoku

Sudoku|数独|sūdoku|is a logic-based 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 often provides a partially completed grid, which typically has a unique solution.

Completed puzzles are always a type of Latin square. This means, each digit occurs exactly once in each row and once in each column. Sudoku rules also place more restrictions on the contents of individual regions: the same single integer may not appear twice

• in the same 9x9 playing board row
• in the same 9x9 playing board column or
• in any of the nine 3x3 subregions of the 9x9 playing board.[1]

The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number.[2] It became an international hit in 2005.[3]

## 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 Denis Berthier proved in his book The Hidden Logic of Sudoku (May 2007) 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). (Citation taken from p. 76 of the first edition: "any block-free resolution rule is already valid in the theory of Latin Squares extended to candidates" – which is restated more explicitly in the second edition, p. 86, as: "a block-free formula is valid for Sudoku if and only if it is valid for Latin Squares").

## References

1. 1 Sudoku.name
2. 2 Brian Hayes. Unwed Numbers
3. 3 So you thought Sudoku came from the Land of the Rising Sun ... The puzzle gripping the nation actually began at a small New York magazine by David Smith The Observer, Sunday May 15, 2005 Accessed June 13, 2008

Acknowledgements

This web page reuses material from Wikipedia page http://en.wikipedia.org/wiki/Sudoku under the rights of CC-BY-SA license. As a result, the content of this page is and will stay available under the rights of this license regardless of restrictions that apply to other pages of this website.