COMPUTING SCIENCE

# Unwed Numbers

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

A Satisfied Mind

From a computational point of view, Sudoku is a constraint-satisfaction problem. The constraints are the rules forbidding two cells in the same neighborhood to have the same value; a solution is an assignment of values to cells that satisfies all the constraints simultaneously. In one obvious encoding, there are 810 constraints in an order-3 grid.

It's interesting to observe how differently one approaches such a problem when solving it by computer rather than by hand. A human solver may well decide that logic is all you need, but backtracking is the more appealing option for a program. For one thing, backtracking will always find the answer, if there is one. It can even do the right thing if there are multiple solutions or no solution. To make similar claims for a logic-only program, you would have to prove you had included every rule of inference that might possibly be needed.

Backtracking is also the simpler approach, in the sense that it
relies on one big rule rather than many little ones. At each stage
you choose a value for some cell and check to see if this new entry
is consistent with the rest of the grid. If you detect a conflict,
you have to undo the choice and try another. If you have exhausted
all the candidates for a given cell, then you must have taken a
wrong turn earlier, and you need to backtrack further. This is not a
clever algorithm; it amounts to a depth-first search of the tree of
all possible solutions—a tree that could have 9^{81}
leaves. There is no question that we are deep in the exponential
territory of NP problems here. And yet, in practice, solving Sudoku
by backtracking is embarrassingly easy.

There are many strategies for speeding up the search, mostly focused on making a shrewd choice of which branch of the tree to try next. But such optimizations are hardly needed. On an order-3 Sudoku grid, even a rudimentary backtracking search converges on the solution in a few dozen steps. Evidently, competing against a computer in Sudoku is never going to be much fun.

Does that ruin the puzzle for the rest of us? In moments of
frustration, when I'm struggling with a recalcitrant diabolical, the
thought that the machine across the room could instantly sweep away
all my cobwebs of logic is indeed dispiriting. I begin to wonder
whether this cross-correlation of columns, rows and blocks is a fit
task for the human mind. But when I *do* make a breakthrough,
I take more pleasure in my success than the computer would.

© Brian Hayes

EMAIL TO A FRIEND :

**Of Possible Interest**

**Spotlight**: Briefings

**Technologue**: Quantum Randomness

**Letters to the Editors**: Nautilus Biology