The Chaos within Sudoku: Mathematics of Sudoku Leads To "Richter Scale" of Puzzle Hardness | wiwisL |

The most difficult known Sudoku puzzle has 'Richter scale' rating of 3.6, according to a new mathematical description of puzzle hardness. But there could be harder puzzles out there. 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.

Via Dr. Stefan Gruenwald