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
» Post Comment