In my earlier post on sudoku below, I referred to Brian Hayes’ column on the mathematical concepts behind it. Here is Hayes’ American Scientist essay:
“Rather than discuss methods for solving specific puzzles, I want to ask some more-general questions about Sudoku, and look at it as a computational problem rather than a logic puzzle. How hard a problem is it? Pencil-and-paper experience suggests that some instances are much tougher than others, but are there any clear-cut criteria for ranking or classifying the puzzles?”
