Oh noes! The puzzle craze of 2006 is rooned!
It’s fiendish, it may even be diabolical, and it’s the solution to Sudoku. To the outrage of the puzzle’s 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 sudokus 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 variations 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 overhyped 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.
Great post!
I don’t do Sudoku that often, but when I do I often find myself running through the possibilities in my head, comparing and contrasting different possibilities. (I’m not a good player.) If I did do them more often I’d be quite interested in this.
When I was a kid I used to like doing things like devising the ‘perfect’ game of Patience (or Solitaire as they call it in the US). I did this by arranging the cards so that, as soon as you dealt them out you were able to arrange them in their various suits and win the game (with a normal pack of 52 cards it’s impossible). Sometimes I’d even try and ‘invent’ new card games.
I don’t think in general there is any one sacred or sacrosanct way to approach games and amusements like card games or Sudoku – James Crook’s approach provides an interesting fresh perspective on the game.
In other news, a device has been invented which has a similar effect on crossword puzzles and games of Scrabble. Called a dictionary, it contains every word that could be used in those games. Reports that dictionaries preceded these games, and that they continue in popularity regardless, have been described as “a cheap shot”.
Further studies at the Merkel Institute have shown that any fool in a tinny can travel across water faster than Libby Trickett can swim, and that most hoons in appalling old bombs of cars can travel faster than Usain Bolt can run. Stirling Mortlock could also run faster, and suffer less inconvenience and injury, were he to do so without feeling obliged to carry a rugby ball. I could go on.
There’s a guy here at the university that wrote a genetic algorithm program that he demonstrated to the rest of us mouth breathers by having it solve sudoku puzzles on the screen of the computer.
It knows the rules of the game, but devises fiendish little formulas of fitness for solutions by ranking them according to correctness, then modifying the solutions a bit and tries the new ones for fitness. It’s a brute force version of the hard coded algorithm described above and is fascinating to watch.
I’m not sure why Andrew E isn’t impressed – as a comment on the parlous state of science reporting Roberts piece is interesting. I’m not sure the whole “technology beats humans at boring tasks, news at 11″ idea is even mentioned.
For me the purpose of Sudoku is to occupy me so intensely that I reach my bus, plane, or train destination without being aware of the time it has taken. Crook should address the issue of how we can add meaning to a life lived in transit, rather than try to spoil our Sudoku.
I found this article very helpful in debunking the sensationalist press. I didn’t feel like reading through 9 pages of someone’s else math scribbles so I’m grateful that there are people that did.
I also don’t feel that this story deserves such attention as it brings no new information (just a fancy article about something that any grad student in math or computer science could come up with) and the title is an outright fabrication. This has been a standard in journalism for years now, so many will probably not find it surprising. But to me it’s sad that there are people who buy into such stories and repeat them forever just because they read it in the newspaper.
“… it’s a textbook example of the kind of lousy science coverage we usually get in the mainstream media.”
Yes, they just cranked it out by the numbers didn’t they?
Good tear up and too true. Solutions for Sudoku are legion. I’ve seen solutions in at least Java, C, Haskell and (really) SQL.
The human ‘methods’ for solving Sudoku might come in handy for an A* search, I figure. More mindblowing is the way you can get a computer to invent its own heuristics for you.
This is why the lay person thinks we do magic, Mr Merkel. Because we take their brutal mind-crushers, sniff dismissively about trivial search problems, and go back to the Hard Problems.
Jacques @ 7, you’ve just expressed beautifully why I could never get excited about Sudoko. (My late mother loved them, although she could have been a good mathematician if she’d put her mind to it.)
It’s trivial.
I always thought Sudoku’s were cranked out by the numbers as well.
Many crossword businesses these days produce their crosswords mostly through computer programs, with checkers to verify word spellings, and make sure they clues/answers aren’t too hard/easy. And crosswords require significantly more human input and imagination in their creation than Sudoku.
Once more, the cryptic crossword firms up as the only real contender for proper human puzzling.
“Crook should address the issue of how we can add meaning to a life lived in transit”
Brilliant! Although I respectfully submit that the answer is, simply, a novel.
Laura
It is a matter too of balance: Sometimes a novel, sometimes Sudoku…
Dodgy stuff is legion in articles about puzzles. An article about the (London) Times cryptic crossword is pretty sure to include the tale of the Provost of Eton who supposedly used his daily attempt to time his breakfast egg-boiling. Nearly as patently false as “the great wall of China is the only man-made object visible from space/the moon” when you discover how much solving times vary, even for experts.
Crosswords and computers: There is a program called Crossword Maestro which does a pretty good job of solving cryptic crosswords. But as far as cryptic xwds are concerned, the only attempt so far made (in the UK at least) to computerise the production process was not a success, and a canny campaign by its xwd setters ensured that a lot of humble pie had to be consumed by the newspaper concerned.
Alright! We got a real player in here.
So Peter any truth to the great story about some Bletchly Park code wranglers being recruited through their speed at solving the Times crossword?
A few years ago I made inquiries about possibly employment at a large crossword publisher/compiler in Australia. I came away with the impression that most of the process of putting together crosswords (either quick or cryptic) together were computer driven…. the crossword pattern, and the words, could be generated; and as for the clues, well, I think they had a large database of them to be re-used on certain words.
It’s not so much a question of thinking up ‘new’ clues for every word, but either using a pre-existing clue, or applying existing rules to come up with another one. (If you pick up one of their books many of the clues will be easily identifiable in this way.)
I’d imagine there are plenty of other medium to large crossword publishers/producers who use computers in a similar way. The pressures of regular publication would be too much otherwise.
Computer-made puzzles: I guess it depends where you go for your crosswords. In the UK, the puzzles for at least the 5 “broadsheet” papers (Times, FT, Telegraph, Guardian, Independent) are written by humans using original clues (some old chestnuts get repeated). The same is true for their non-cryptic puzzles. I’m not aware of any UK national newspaper cryptic puzzle that’s produced by computers. I don’t know much about the Australian market, but I’m sure the SMH cryptic puzzles are by humans. So is the “Stickler” puzzle (in a “something Telegraph” paper?), and the puzzle in the Australian is syndicated from the (London) Times. If I saw “easily identifiable” machine made-clues for a puzzle I would be very unlikely to continue solving it.
The Bletchley Park story: except that it was the Telegraph puzzle that they were timed on, the story is apparently true. 12 minutes or less and you were in, I believe.