Sudoku and Mathematics


[Source: Brainbashers. Solution below]

Everyone is talking about Sudoku, so I tried it and was, predictably perhaps, instantly addicted.

The Christian Science Monitor article sums up the game pretty nicely:

Sudoku, which means "single number" in Japanese, is essentially a simple logic problem with layers of hidden complexity that can draw the solver in to the point of obsession. A grid nine squares by nine is presented in which all the integers from 1 to 9 must appear in every row, every column and every 3-by-3 box. So far, so good.

Some numbers are given as initial clues. Then, by process of deduction, sometimes resorting to quite intense logical assumptions, the solver can slowly begin to work out what goes where.

There is a debate at Jabberwock about whether the skills involved in solving the puzzles are or aren't "math." A Financial Times article is referenced, only I don't subcribe to the FT, so I can't read it. It's a safe bet to say that the game requires intensive use of heuristic logic; perhaps it doesn't matter whether we use the "M" word or not.

The CSM article references two terms I hadn't seen before in connection with this question, in the following sentence:

Thus more committed fans will engage you in subtleties of bifurcation and Ariadne threads, of trial and error versus pure logic.

From a quick Googling, all I can get on "bifurcation" is some stuff Fractal algorithms, which doesn't seem at all relevant to Sudoku. And "Ariadne's thread," in mythology, was a gift Ariadne gave her lover to help him get through a labyrinth. In everyday usage, an "Ariadne thread" refers to a heuristic you use to help retrace a line of thought. Presumably in Sudoku it would relate to keeping track of a trail of hypotheticals or guesses. But again, I couldn't find anything that would explain what exactly the technical, mathematical reference point for "Ariadne Threads" might be. There is something going on with this in serious Computer Science-land, but I can't make heads or tails of it.

Update: There is some good math on Sudoku at Wikipedia, but this is more the way a computer would solve the grid as an "NP-Complete" problem, not so much a human.

For more on Sudoku, see of course Slate, Puzzle Cannon, and especially Locana.

Anand points to Web Sudoku, which might be a good place to get started if you're not looking to install the game software from Sudoku.com.