Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

Unwed Numbers

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

Brian Hayes

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 981 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




comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Spotlight: Briefings

Technologue: Quantum Randomness

Letters to the Editors: Nautilus Biology

Subscribe to American Scientist