Mathematics of Sudoku Leads To "Richter Scale" of Puzzle Hardness
THE PHYSICS ARXIV BLOG
Monday, August 6, 2012
The global fascination with Sudoku has led to a sudden interest in the mathematical properties of the puzzle. In the last few months on this blog, we've looked at how mathematicians have solved the minimum Sudoku problem and even how they've used the mathematics of Sudoku to encrypt images.
Today, we get a different take on Sudoku thanks to the work of Maria Ercsey-Ravasz at Babes-Bolyai University in Romania and Zoltan Toroczkai at the University of Notre Dame in Indiana.
These guys have developed a way to measure the difficulty of a particular Sudoku puzzle and say their "Richter scale" of puzzle difficulty could be applied to a wide range of other games.
...
They start by inserting a random set of numbers into the grid and follow the algorithm's trajectory through state space as it searches for a solution. For a simple problem, that trajectory is simple, as shown in the upper of the two figures at the top of this post.
But all that changes for a difficult problem. Ercsey-Ravasz and Toroczkai test their algorithm against a Sudoku grid so hard that it has its own name: the platinum blond. The result is shown in the bottom half of the figure. It is considerably more complex and takes ten times as long to solve.
more
http://www.technologyreview.com/view/428729/mathematics-of-sudoku-leads-to-richter-scale-of/
= new reply since forum marked as read