COMPUTING SCIENCE
Unwed Numbers
The mathematics of Sudoku, a puzzle that boasts "No math required!"
Brian Hayes
Logic Rules
Many puzzle constructors distinguish between puzzles that can be
solved "by logic alone" and those that require "trial
and error." If you solve by logic, you never write a number
into a cell until you can prove that only that number can appear in
that position. Trial and error allows for guessing: You fill in a
number tentatively, explore the consequences, and if necessary
backtrack, removing your choice and trying another. A logic solver
can work with a pen; a backtracker needs a pencil and eraser.
For the logic-only strategy to work, a puzzle must have a quality of
progressivism: At every stage in the solution, there must be at
least one cell whose value can be determined unambiguously. Filling
in that value must then uncover at least one other fully determined
value, and so on. The backtracking protocol dispenses with
progressivism: When you reach a state where no choice is forced upon
you—where every vacant cell has at least two
candidates—you choose a path arbitrarily.
The distinction between logic and backtracking seems like a
promising criterion for rating the difficulty of puzzles, but on a
closer look, it's not clear the distinction even exists. Is there a
subset of Sudoku puzzles that can be solved by backtracking but not
by "logic"? Here's another way of asking the question: Are
there puzzles that have a unique solution, and yet at some
intermediate stage reach an impasse, where no cell has a value that
can be deduced unambiguously? Not, I think, unless we impose
artificial restrictions on the rules allowed in making logical deductions.
Backtracking itself can be viewed as a logical operation; it
supplies a proof by contradiction. If you make a speculative entry
in one cell and, as a consequence, eventually find that some other
cell has no legal entry, then you have discovered a logical relation
between the cells. The chain of implication could be very intricate,
but the logical relation is no different in kind from the simple
rule that says two cells in the same row can't have the same value.
(David Eppstein of the University of California at Irvine has
formulated some extremely subtle Sudoku rules, which capture the
kind of information gleaned from a backtracking analysis, yet work
in a forward-looking, nonspeculative mode.)
» Post Comment