What is Sudoku?
Written by BuySudokuPuzzles.com Introduction to Sudoku (pronounced SUE-dough-coo)
It's a wordless crossword puzzle that leaves even the best puzzle solvers scratching their head. It is unique in that there is no math involved and you don't even have to know a certain language to play. It's just pure logic. And people love it. It has universal appeal to all ages because it is easy to learn but may take a lifetime to master. People who enjoy logic based puzzles will love the fresh challenge of Sudoku.
How to play
The attraction of the puzzle is that the rules are simple. So simple, in fact, that they can be stated in one sentence.
The goal of the puzzle is to fill in every empty cell in the 3x3 regions with the numbers 1 through 9, and make sure all rows and columns of the 9x9 puzzle have the number 1-9 only once.Sounds simple right? Let's take a look at a typical Sudoku grid:
Each puzzle starts with some numbers already filled in (called givens) to make the puzzle unique and to give you clues on how to start. In order to be considered a true "Sudoku", every puzzle must only have one unique solution.
The solving strategies for a Sudoku puzzle can go from easy to advanced, so we have made another section to cover solving strategies. If you are interested in solving strategies, please visit our section on Sudoku solving strategies. For more information on the mathematics and the origin and history of Sudoku please continue reading.
Mathematics of Sudoku
The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
Solving Sudoku puzzles (as well as any other NP-hard problem) can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labeled with the ordered pairs (x,y), where x and y are integers between 1 and 9. In this case, two distinct vertices labeled by (x,y) and (x',y') are joined by an edge if and only if: x = x', or, y = y', or, ceil(x/3) = ceil(x'/3) and ceil(y/3) = ceil(y'/3)
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid has been calculated to be 6,670,903,752,021,072,936,960. This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. When symmetries were taken into account, there are 5,472,730,538 essentially different Sudoku grids.
History of Sudoku
The puzzle was originally designed anonymously by Howard Garns, a 74-year-old retired architect and freelance puzzle constructor, and first published in 1979. Although likely inspired by the Latin square invention of Leonhard Euler, Garns added a third dimension (the regional restriction) to the mathematical construct and (unlike Euler) presented the creation as a puzzle, providing a partially-completed grid and requiring the solver to fill in the rest. The puzzle was first published in New York by the specialist puzzle publisher Dell Magazines in its magazine Dell Pencil Puzzles and Word Games, under the title "Number Place".
The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as "Suuji wa dokushin ni kagiru", which can be translated as "the numbers must be single" or "the numbers must occur only once". The puzzle was named by Kaji Maki, the president of Nikoli. At a later date, the name was abbreviated to Sudoku (su = number, doku = single); it is a common practice in Japanese to take only the first kanji of compound words to form a shorter version. In 1986, Nikoli introduced two innovations which guaranteed the popularity of the puzzle: the number of givens was restricted to no more than 32 and puzzles became "symmetrical" (meaning the givens were distributed in rotationally symmetric cells). It is now published in mainstream Japanese periodicals, such as the Asahi Shimbun. Within Japan, Nikoli still holds the trademark for the name Sudoku; other publications in Japan use alternative names.
In 1989, Loadstar/Softdisk Publishing published DigitHunt on the Commodore 64, which was apparently the first home computer version of Sudoku. At least one publisher still uses that title.
Yoshimitsu Kanai published his computerized puzzle generator under the name Single Number for the Apple Macintosh in 1995 in Japanese and English, for the Palm (PDA) in 1996, and for the Mac OS-X in 2005.
Bringing the process full-circle, Dell Magazines, which publishes the original Number Place puzzle, now also publishes two Sudoku magazines: Original Sudoku and Extreme Sudoku. Additionally, Kappa reprints Nikoli Sudoku in GAMES Magazine under the name Squared Away; the New York Post, USA Today, The Boston Globe, Washington Post, and San Francisco Chronicle now also publish the puzzle. It is also often included in puzzle anthologies, such as The Giant 1001 Puzzle Book (under the title Nine Numbers).
Within the context of puzzle history, parallels are often cited to Rubik's Cube, another logic puzzle popular in the 1980s. Sudoku has been called the "Rubik's cube of the 21st century".
