Weblog > Your sudoku will not be spoiled
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]