Oh noes! The puzzle craze of 2006 is ruined. Itís fiendish, it may even be diabolical, and itís the solution to Sudoku. To the outrage of the puzzle fans, an American computer scientist will tomorrow reveal a formula for solving any Sudoku problem, no matter how difficult.
The Crook algorithm is the first mathematical proof of how to solve the puzzle. Not even Howard Garns, the Indianapolis architect who devised Sudoku in 1979, could promise that.
For better or worse, reports of the the death of Sudoku through the works of James Crook are greatly exaggerated.
If youíre not familiar with Sudoku (what rock were you living under?) itís a type of logic puzzle played on a 9◊9 (in the standard version) grid, further subdivided into 9 3◊3 ďboxesĒ. The player is given a Sudoku grid partially filled in with single digits, and has to fill in the remaining digits according to a simple rule – every row, column, and box must contain each digit 1 to 9 precisely once.
For a computer scientist, this is a straightforward example of something called a finite-domain constraint satisfaction problem. These are, in general, ďhardĒ problems, in that as the problems become bigger, they rapidly become impossible to solve in a reasonable time. But at the scale of a 9◊9 Sudoku, this isnít an issue, and standard ďbacktrackingĒ techniques solve most Sudoku’s in the blink of an eye. Itís completely and utterly a solved problem.
How is this miracle achieved? In essence, you fill out the squares using the obvious techniques (for instance, if thereís only one possibility for a particular grid position, fill it in), until youíve done all you can with the obvious techniques. At that point, you pick one of the other squares and take a guess. Either the guess will be correct and you continue on your merry way, or it forces a violation of the Sudoku rules. You then ďbacktrackĒ to where you made the guess, and choose one of the other possibilities. This may sound slightly complicated, but itís a beginning exercise in computer programming. And there are a number of Sudoku variants which can be used to speed the process up considerably.
But itís not generally how Sudoku players like to solve puzzles; guessing is generally considered a cop-out. Instead, they have identified more complicated patterns with fancy names like x-wing and chaining. Theyíre just slightly harder (for humans) to spot patterns for eliminating certain possibilities from consideration, thus avoiding the need for guessing. Itís possible to build computer programs that use these fancier elimination rules to solve Sudoku puzzles; theyíre useful for puzzle designers, because they give a good insight into how difficult a particular puzzle will be for its human players. But theyíre not necessary to actually solve a puzzle – just the very simplest rules, and backtracking, will do the job.
So what insight does Crookís paper offer? Essentially, he proposes an alternative – and not significantly easier to understand or perform – mathematical description of the simple techniques every Sudoku player knows. And if they donít work? You guessed it – or more to the point, his technique guesses. Itís just backtracking search, a technique thatís been around longer than Sudoku itself.
Sudoku players arenít going to start using this method for two very good reasons: a) it takes all the fun out of it, and b) itís generally much slower than using the advanced solution-elimination techniques. All itís useful for is a fallback method for finding a solution when youíre stuck, and, frankly, if you want to do that you may as well enter it in to a computer and let it handle the tedious work for you.
The Times reporters who broke this non-story seem to have spoken to a Sudoku champion (and undergraduate mathematics student) and a Sudoku puzzle compiler. Given the idiocies in this story, I have to wonder whether they actually listened to their answers. That said, whomever was responsible for promoting this story to the Times has clearly over-hyped the story.
While itís of no great consequence here, itís a textbook example of the kind of lousy science coverage we usually get in the mainstream media. Happy Puzzling! [via Larvatus Prodeo]