Mathematicians create "Richter scale" of Sudoku difficulty

(CBS News) Sudoku is, at its heart, a numbers game. So it's no surprise that mathematicians have latched on to the puzzles as a way to explore problem-solving algorithms and game theories. For dedicated number crunchers, it's not terribly hard to "brute force" Sudoku puzzles by running dozens if not hundreds of possible combinations in search of the right answer. But a team of researchers has discovered a more elegant solution, and in the process have created a "Richter scale" of puzzle difficulty.

Maria Ercsey-Ravasz, of Romania's Babes-Bolyia University and Zoltan Toroczkai of Notre Dame University in Indiana, recently published a paper in "Applied Physics Letters" detailing their work on Sudoku-solving algorithms that move far beyond the simpler "brute force" systems already used by dedicated Sudoku enthusiasts.

A brute force system simply runs all possible combinations of numbers on a Sudoku board until the correct answer is found. The system works, and according to Ercsey-Ravasz and Toroczkai, it is relavitely easy to set up, but the answers take time to arrive.

The more advanced algorithms created by Ercsey-Ravasz and Toroczkai are much more complex, but can arrive at the correct number combinations far quicker. The two mathematicians realized that the time it took to solve a Sudoku board correlated to the difficulty of the puzzle. This led them to create what they called a "Richter scale" of game difficulty.

Their scale goes from 1 to 4, and the numbers line up almost perfectly with the stated difficulty of a puzzle. Sudoku games are generally classified as "Easy" to "Hard" and the pair found that a 1 on their scale was almost always an easy puzzle. A 3 on their scale was almost always a hard puzzle.

They tested their model on one of the hardest Sudoku puzzles known - a game so hard it has its own name: "Platinum Blonde." This ultra-difficult puzzle (the lower puzzle in the above image) had a difficulty of 3.5789 on the Richter scale and took almost ten times as long for the algorithm to complete as an easy board.

Ercsey-Ravasz and Toroczkai hope to expand their algorithm models to incorporate more than just Sudoku. Their findings could point the way for more algorithmic difficulty scales over a wide array of numbers problems in the future.