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 
square is divided into 
"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).
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, 
. Harder grids require the "forcing chains" technique.
Above, any value of 
forces 
, since
 |
The numbers of completed Sudokus of size 
for 
, 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 
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.
Royle has compiled more than 
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 
(Boyer 2006; http://www.multimagie.com/PanSudoku25x25.pdf).
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 
region. Conveniently, this number is the given in that
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.
Agmon-Snir, H. "Sudoku
Analysis in Mathematica."