COMPUTING SCIENCE
Unwed Numbers
The mathematics of Sudoku, a puzzle that boasts "No math required!"
Brian Hayes
Hints and Heuristics
If you take a pencil to a few Sudoku problems, you'll quickly
discover various useful rules and tricks. The most elementary
strategy for solving the puzzle is to examine each cell and list all
its possible occupants—that is, all the numbers not ruled out
by a conflict with another cell. If you find a cell that has only
one allowed value, then obviously you can write that value in. The
complementary approach is to note all the cells within a row, a
column or a block where some particular number can appear; again, if
there is a number that can be put in only one position, then you
should put it there. In either case, you can eliminate the selected
number as a candidate in all other cells in the same neighborhood.
Some Sudoku can be solved by nothing more than repeated application
of these two rules—but if all the puzzles were so
straightforward, the fad would not have lasted long. Barry Cipra, a
mathematician and writer in Northfield, Minnesota, describes a
hierarchy of rules of increasing complexity. The rules mentioned
above constitute level 1: They restrict a cell to a single value or
restrict a value to a single cell. At level 2 are rules that apply
to pairs of cells within a row, column or block; when two such cells
have only two possible values, those values are excluded elsewhere
in the neighborhood. Level-3 rules work with triples of cells and
values in the same way. In principle, the tower of rules might rise
all the way to level 9.
This sequence of rules suggests a simple scheme for rating the
difficulty of puzzles. Unfortunately, however, not all Sudoku can be
solved by these rules alone; some of the puzzles seem to demand
analytic methods that don't have a clear place in the hierarchy. A
few of these tactics have even acquired names, such as
"swordfish" and "x-wing." The subtlest of them
are nonlocal rules that bring together information from across a
wide swath of the matrix.
When you are solving a specific puzzle, the search for patterns that
trigger the various rules is where the fun is (assuming you go in
for that sort of thing). But if you are trying to gain a
higher-level understanding of Sudoku, compiling a catalog of such
techniques doesn't seem very promising. The rules are too many, too
various and too specialized.
Rather than discuss methods for solving specific puzzles, I want to
ask some more-general questions about Sudoku, and look at it as a
computational problem rather than a logic puzzle. How hard a problem
is it? Pencil-and-paper experience suggests that some instances are
much tougher than others, but are there any clear-cut criteria for
ranking or classifying the puzzles?
» Post Comment