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

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

 

EMAIL TO A FRIEND :

Of Possible Interest

Feature Article: Twisted Math and Beautiful Geometry

Perspective: Searching for Great Adventures

Letters to the Editors: Prime Beef

Subscribe to American Scientist