TOPICS
Search

Sudoku


Sudoku

Sudoku (literally, "single number"), sometimes also is a pencil-and-paper logic puzzle whose goal is to complete a grid satisfying various constraints. In the "classic" Sudoku, a 9×9 square is divided into 3×3 "regions", with various squares filled with "givens." Valid solutions use each of the numbers 1-9 exactly once within each row, column and region. This kind of sudoku is therefore a particular case of a Latin square.

Under the U.S.-only trademarked name "Number Place," Sudoku was first published anonymously by Garns (1979) for Dell Pencil Puzzles. In 1984, the puzzle was used by Nikoli with the Japan-only trademarked name Sudoku (Su = number, Doku = single). Due to the trademark issues, in Japan, the puzzle became well-known as nanpure, or Number Place, often using the English name. Outside Japan, the Japanese name predominates.

The puzzle received a large amount of attention in the United States and Europe in 2005 after a regular Sudoku puzzle began appearing in the London Times. Sadly, Garns died in 1989 before getting a chance to see his creation as a worldwide phenomenon (Shortz 2005, cited in Pegg 2005).

SudokuChains

The process known as "scanning" involves analyzing a cell for possible values, and filling cells where only one number is possible. Scanning alone will solve most simple Sudoku puzzles. In the grid above, x=1. Harder grids require the "forcing chains" technique. Above, any value of a forces f=2, since

 a=1->b=8->c=7->f=2
a=2->d=9->e=7->f=2.

The numbers of completed Sudokus of size n^2×n^2 for n=1, 2, ... are 1, 288, 6670903752021072936960, ... (OEIS A107739; Felgenhauer et al. 2005). Similarly, the numbers of inequivalent (i.e., reduced modulo symmetries) completed Sudokus are 1, 2, 5472730538, ... (OEIS A109741; Felgenhauer et al. 2005). (For example, for the 9×9 case the allowed equivalences are: relabeling entries; reflection; rotation; permutation of blocks of columns 1-3, 4-6, and 7-9; permutation of blocks of rows 1-3, 4-6, and 7-9; permutation of columns 1-3; permutation of rows 1-3; permutation of columns 4-6; permutation of rows 4-6; permutation of columns 7-9; and permutation of rows 7-9.)

These facts were noted by math genius Charlie Eppes when discussing the relative merits of recreational solving of puzzles versus writing computer programs to solve them in the Season 2 episode "All's Fair" (2006) of the television crime drama NUMB3RS.

Sudoku16

Royle has compiled more than 30000 17-clue Sudoku puzzles with unique solutions. His analysis of the existing 17-clue examples has revealed a structurally unique 16-clue Sudoku that has exactly two solutions (illustrated above). Whether another exists with either one or two solutions is unknown.

The smallest possible pandiagonal sudoku is 25×25 (Boyer 2006; http://www.multimagie.com/PanSudoku25x25.pdf).

MagicSudoku

Many variants of Sudoku exist. Some use non-square regions. Others require that the main diagonals use all nine digits. The puzzle above has the diagonal requirement. In addition, each number inside the polyomino (blue cells) must be no larger than the number of blue cells in its 3×3 region. Conveniently, this number is the given in that 3×3 square (A. O. Muniz, pers. comm., Aug. 19, 2005).

According to research by C. Boyer, in the 1890's, many french newspapers and magazines (Le Siècle, La France, Gil Blas, l'Echo de Paris, Les Tablettes du Chercheur, and La Revue des Jeux) featured puzzles which are similar to Sudoku.


See also

Euler Square, Latin Square

Portions of this entry contributed by Ed Pegg, Jr.

Explore with Wolfram|Alpha

References

Abbott, P. (Ed.). "In and Out: In-Flight Puzzle." Mathematica J. 9, 528-531, 2005. Agmon-Snir, H. "Sudoku Analysis in Mathematica." http://library.wolfram.com/infocenter/MathSource/5691/.Armstrong, S. "Forcing Chains." http://www.simes.clara.co.uk/programs/sudokutechnique7.htm.Boyer, C. "Letters: Magic Squares." Math. Today 42, 70, Apr. 2006.Boyer, C. "Sudoku's French Ancestors." Pour la Science. June 2006.http://www.mathpuzzle.com/SudokuAncestors.pdf.Delahaye, J.-P. "The Science Behind Sudoku." Sci. Amer. 294, 80-87, Jun. 2006.Felgenhauer, B. and Jarvis, F. "There Are 6670903752021072936960 Sudoku Grids." 2005. http://www.shef.ac.uk/~pm1afj/sudoku/.Garns, H. "Number Place." Dell Pencil Puzzles & Word Games. No. 16, May p. 6, 1979. McLoone, J. "Sudoku Solver." http://library.wolfram.com/infocenter/MathSource/5690/."Pandiagonal Sudoku." Math. Today, p. 70, Apr. 2006.Pegg, E. Jr. "Math Games: Sudoku Variations." Sept. 6, 2005. http://www.maa.org/editorial/mathgames/mathgames_09_05_05.html.Rothstein, E. "In Sudoku, 9 Little Numbers Create a Big Challenge." The New York Times, pp. B1 and B4, May. 1, 2006.Royle, G. "Minimum Sudoku." http://www.csse.uwa.edu.au/~gordon/sudokumin.php.Royle, G. "Sudoku Patterns." http://www.csse.uwa.edu.au/~gordon/sudokupat.php.Russell, E. and Jarvis, F. "There are 5472730538 Essentially Different Sudoku Grids." http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html.Shortz, W. Sudoku Easy: 100 Wordless Crossword Puzzles. New York: St. Martin's Griffin, 2005.Shortz, W. "A Few Words About Sudoku, Which Has None." The New York Times. Sunday, Aug. 28, 2005."Sudoku: The Biggest Sudoku Links List." http://sudoku.jouwpagina.nl/.Sloane, N. J. A. Sequences A107739 and A109741 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Sudoku

Cite this as:

Pegg, Ed Jr. and Weisstein, Eric W. "Sudoku." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Sudoku.html

Subject classifications