The rules are simple. The puzzles can be very challenging—and highly addictive.
Millions of people in Japan, Great Britain, and elsewhere around the world are finding that a day isn’t complete without tackling the latest edition of a simple puzzle called sudoku. Sudoku means “single number” in Japanese.
The puzzle typically consists of a nine-by-nine grid. Some of the spaces contain numbers; most of the spaces are blank. Your goal is to fill in the blanks with digits from 1 to 9 so that each row, each column, and each of the nine three-by-three blocks making up the grid contains just one of each of the nine digits.
It’s basically a logic puzzle; there’s no math involved in solving it. The digits could just as easily be nine different letters, shapes, or colors. There is mathematics and computer science, however, in analyzing the puzzles and creating efficient computer programs for generating and solving them.
A sudoku grid is a special case of a mathematical object called a Latin square. A Latin square consists of n sets of numbers from 1 to n arranged in a square pattern so that no row or column contains the same number twice. There are two Latin squares of order two (n = 2), 12 of order three, and 576 or order four.
Order |
No. of Latin squares |
1 |
1 |
2 |
2 |
3 |
12 |
4 |
576 |
5 |
161280 |
6 |
812851200 |
7 |
61479419904000 |
8 |
108776032459082956800 |
9 |
5524751496156892842531225600 |
10 |
9982437658213039871725064756920320000 |
Latin squares go back to at least medieval times. Leonhard Euler (1707–1783) was the first mathematician to study them systematically. He introduced a particular type of Latin square (a Graeco-Roman square) as a new kind of “magic square.”
As in sudoku, the rows and columns of a Latin square don’t have to be filled with numbers. Any set of n different symbols will do.
Here’s a five-by-five Latin square based on the word “magic.”
M |
A |
G |
I |
C |
G |
I |
C |
M |
A |
C |
M |
A |
G |
I |
A |
G |
I |
C |
M |
I |
C |
M |
A |
G |
The additional constraint that a standard nine-by-nine sudoku puzzle have three-by-three blocks that also contain each of the nine digits reduces the enormous number of possible nine-by-nine Latin squares to a smaller but still-humungous number: 6,670,903,752,021,072,936,960. See http://www.sudoku.com/forums/viewtopic.php?t=44&start=138 for a discussion on how Bertram Felgenhauer of Dresden, Germany, obtained this number, which represents how many unique, one-solution puzzles can be produced. Given all those possibilities, there’ll certainly be no shortage of material to feed sudoku addiction.
Depending on the number of clues and the size of the grid, sudoku puzzles can be extremely difficult to solve. Takayuki Yato and Takahiro Seta of the University of Tokyo have proved that solving n-by-n sudoku puzzles in general belongs to a category of computational problems described as NP-complete. An NP problem is one for which it’s relatively easy to check whether a given answer is correct but may require an impossibly long time to solve by any direct procedure, especially as n gets larger and larger. Indeed, as the number of elements, n, increases, a computer’s solution time grows exponentially in the worst case.
Solving a sudoku puzzle is equivalent to properly “coloring” a particular graph—an array of points (vertices) and lines (edges). In this case, the graph has 81 vertices, one for each cell of the grid. Depending on the puzzle, only certain pairs of vertices are joined by an edge. Given that some vertices have already been assigned a “color” (chosen from nine possibilities), the problem is to “color” the remaining vertices so that any two vertices joined by an edge don’t have the same “color.”
Nonetheless, there are strategies that computer programmers can use to generate puzzles and find solutions relatively quickly for nine-by-nine grids—and even larger ones.
Are you ready to sudoku?
