[caption id="attachment_1399" align="alignright" width="300"] Sudoku Richter Scale from MIT[/caption]
I have wanted to write a post on Sudoku for a while now--especially computer programs that can solve puzzles or evaluate solutions. This week's Nerd Fun post gives me a chance to bring up the topic, thanks to a recent post at Technology Review.
Sudoku puzzles are generally classified as easy, medium or hard with puzzles having more starting clues generally but not always easier to solve. But quantifying the difficulty mathematically is hard.
Now Ercsey-Ravasz and Toroczkai say they've worked out a way to do it using algorithmic complexity theory. They point out that it's easy to design an algorithm that solves Sudoku by testing every combination of digits to find the one that works. That kind of brute force solution guarantees you an answer but not very quickly.
Instead, algorithm designers look for cleverer ways of finding solutions that exploit the structure and constraints of the problem. These algorithms and their behaviour are are more complex but they get an answer more quickly.
The central point of Ercsey-Ravasz and Toroczkai argument is that because an algorithm reflects the structure of the problem, its behaviour--the twists and turns that it follows through state space--is a good measure of the difficulty of the problem.
To quantify the difficulty of Sudoku puzzles, Ercsey-Ravasz and Toroczkai evaluate the complexity of the problem as the solution progresses. A puzzle does not have a static state of difficulty: the solution gets chaotic before it starts to coalesce. The end result is a type of "Richter scale" for puzzles, although it doesn't go all the way to 10--or even 4, at least not yet.
They say this scale correlates surprisingly well with the subjective human ratings with 1 corresponding to easy puzzles, 2 to medium puzzles and 3 to hard puzzles. The platinum blond has a difficulty of 3.5789.
An interesting corollary is that no Sudoku puzzle is known with a difficulty of 4. And the number of clues is not always a good measure of difficulty either. Ercsey-Ravasz and Toroczkai say they tested many puzzles including several with the 17 clues, the minimum number, and a few with 18 clues.
These were all easier to solve than the platinum blond, which has 21 clues. That's because the hardness of the puzzle depends not only on the number of clues but also on their position as well.