Su Doku is a mathematical puzzle syndicated in some newspapers, notably The Times of London.
Su Doku was created by Wayne Gould.
A 9 by 9 grid is presented with most squares empty and a few having a single digit. The puzzle is to complete the grid such that each column, each row and each of nine non-overlapping 3 by 3 sub-squares has each digit 1 through 9 exactly once.
For example:
. . . . . 7 3 . .
4 8 7 . . 5 . 2 .
. . . 6 9 . . . .
. . 4 3 . . 6 . .
. 9 . . . . . 1 .
. . 8 . . 6 5 . .
. . . . 6 9 . . .
. 1 . 5 . . 4 6 3
. . 5 2 . . . . .
is solved as
9 6 1 8 2 7 3 4 5
4 8 7 1 3 5 9 2 6
5 3 2 6 9 4 1 7 8
7 5 4 3 8 1 6 9 2
3 9 6 7 5 2 8 1 4
1 2 8 9 4 6 5 3 7
8 7 3 4 6 9 2 5 1
2 1 9 5 7 8 4 6 3
6 4 5 2 1 3 7 8 9
Note that it is possible to set starting grids with more than one solution and to set grids with no solution.
Solving Su Doku is essentially a problem in graph coloring. The aim of the puzzle is to construct a proper 9-coloring of a particular graph, given a partial 9-coloring. The graph in question has 81 vertices, one vertex for each square of the grid. The vertices can be labelled with the ordered pairs
, where x and y are integers between 1 and 9. In this case, the vertices labelled by and 
are joined by an edge if and only if:
- x = x' or,
- y = y' or,
-
and 
.
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.
External links
