COMPUTING SCIENCE

# Unwed Numbers

The mathematics of Sudoku, a puzzle that boasts "No math required!"

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?

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: In Defense of Pure Mathematics

**Feature Article**: The Statistical Crisis in Science

**Computing Science**: Clarity in Climate Modeling