Researchers make Sudoku puzzles less puzzling

Oct 11, 2012
A standard 9x9 Sudoku matrix. Image credit: Héctor Rodríguez.

For anyone who has ever struggled while attempting to solve a Sudoku puzzle, University of Notre Dame researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravaz are riding to the rescue. They can not only explain why some Sudoku puzzles are harder than others, they have also developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking.

Toroczkai and Ravaz of Romania's Babes-Boylai University began studying Sudoku as part of their research into the theory of and . They note that most Sudoku use what is known as a "brute force" system to solve problems, combined with a good deal of guessing. Brute force systems essentially deploy all possible combinations of numbers in a until the correct answer is found. While the method is successful, it is also time consuming.

Instead, Toroczkai and Ercsey-Ravaz have proposed a universal analog algorithm which is completely deterministic (no guessing or exhaustive searching) but which always arrives at the correct solution to a problem and does so much quicker.

The researchers also discovered that the time it took to solve a problem with their analog algorithm correlated with the difficulty of the problem as rated by human solvers. This led them to develop a ranking scale for problem or puzzle difficulty. The scale runs from 1 through 4 and it matches up nicely with the "Easy" through

"Hard" to "Ultra-Hard" classification currently applied to Sudoku puzzles. A puzzle with a rating of 2 takes, on average, 10 times as long to solve than one with rating of 1. According to this system, the hardest known puzzle so far has a rating of 3.6 and it is not known if there are even harder puzzles out there.

"I had not been interested in Sudoku until we started working on the much more general class of 'Boolean satisfiability problems," Toroczkai said. "Since Sudoku is a part of this class, it seemed like a good testbed for our solver, so I familiarized myself with it. To me, and to a number of researchers studying such problems, a fascinating question is how far can us humans go in solving Sudoku puzzles deterministically, without backtracking, that is without making a choice at random, then seeing where that leads to and if it fails, restarting. Our analog solver is deterministic—there are no random choices or backtracks made during the dynamics." Toroczkai and Ercsey-Ravasz feel that their analog algorithm can potentially be applied to a wide variety of problems in industry, computer science and computational biology.

The research experience has also made Toroczkai a devotee of Sudoku puzzles.

"Both my wife and I have several Sudoku apps on our iPhones and we must have played thousands of times, racing to get the shortest completion times on all levels," he said. "She often sees combinations of patterns that I completely miss. I have to deduce them. Without paper and pencil to jot down possibilities, it becomes impossible for me to solve many of the puzzles that our solver categorizes as hard or ultra-hard." Toroczkai's and Ercsey-Ravasv's methodology was first published in the journal Nature Physics and its application to Sudoku, appears in the Oct. 11 edition of the journal Nature Scientific Reports.

Explore further: Avatars make the Internet sign to deaf people

Related Stories

Discovery could lead to more difficult Sudoku puzzles

Feb 13, 2010

(PhysOrg.com) -- A new analysis of number randomness in Sudoku matrices could lead to the development of more difficult and multi-dimensional Sudoku puzzles. In a recent study, mathematicians have found that ...

Toy Robot to Solve Sudoku (w/ Video)

Sep 03, 2009

(PhysOrg.com) -- A Swedish programmer, Hans Andersson, has used a Lego Mindstorms NXT kit to develop a robot to solve Sudoku puzzles.

New research reveals brain network connections

Jul 13, 2011

Research conducted by Maria Ercsey-Ravasz and Zoltan Toroczkai of the University of Notre Dame's Interdisciplinary Center for Network Science and Applications (iCeNSA), along with the Department of Physics and a group of ...

Recommended for you

Ride-sharing could cut cabs' road time by 30 percent

3 hours ago

Cellphone apps that find users car rides in real time are exploding in popularity: The car-service company Uber was recently valued at $18 billion, and even as it faces legal wrangles, a number of companies ...

Avatars make the Internet sign to deaf people

Aug 29, 2014

It is challenging for deaf people to learn a sound-based language, since they are physically not able to hear those sounds. Hence, most of them struggle with written language as well as with text reading ...

Chameleon: Cloud computing for computer science

Aug 26, 2014

Cloud computing has changed the way we work, the way we communicate online, even the way we relax at night with a movie. But even as "the cloud" starts to cross over into popular parlance, the full potential ...

User comments : 8

Adjust slider to filter visible comments by rank

Display comments: newest first

VINDOC
1.5 / 5 (12) Oct 11, 2012
If you think Sudoku puzzles are hard, you show your level of intelligence. This study is a waste of time. It proves most people don't know patterens. This is a waste of time and my tax money.
El_Nose
3.8 / 5 (6) Oct 11, 2012
That is funny because Sudoku is about elimination. Sudoku problems commonly come with very little in the way of explanation. Now those people who go to the internet for how to solve tend to know the most common.

This cost you no tax money as Notre Dame is a private university.

This is actually a good postdoc project, as Sudoku is a math problem disguised as a game.
fzk44
4.5 / 5 (10) Oct 11, 2012
VINDOC: If you actually read the paper you'll see that it is about optimization problems in general, Sudoku is used as an illustration. Optimization problems, however are everywhere, in every facet of technology. So this might make your life a little better down the line, in spite the fact that you have not paid anything for it (U. Babes-Bolyai is non-US and Notre Dame is private). There is lots of free science and innovation that goes into products ultimately benefiting everyone. Compared to where we were 2000 yrs ago, we have advanced tremendously technologically thanks to science. But the amount of funds poured into science as compared to other things like wars, etc. in the same period is very very small. Nothing gives you a better return on investment in the long run than science.
cantdrive85
2.6 / 5 (5) Oct 11, 2012
I'm stuck in a sudoku matrix, even my iPhone is a victim.
antialias_physorg
5 / 5 (2) Oct 12, 2012
This is actually a good postdoc project, as Sudoku is a math problem disguised as a game.

Agreed. The solver is just one application for an entire range that such an algorithm can be used for.
It proves most people don't know patterens. This is a waste of time and my tax money.

This isn't about Sudoku - this is about information theory. Before you understand even such a simple 'pattern' you shouldn't try to comment on science (or even try to solve a Sudoku puzzle)
evropej
1 / 5 (1) Oct 12, 2012
I have taken a stab at this and made a program to help solve with predicted methods rather than guessing. If anyone wants to try it out, its freeware
http://evropej.co...v2.9.zip

Here is a quick tutorial on the program
http://evropej.co...oku.html

The program is hosted on freewarefiles.com
I love the game, it keeps my mind sharp.
Bowler_4007
not rated yet Oct 15, 2012
Has anyone got a link to their work, the 2 links at the end of the article have thus far proved useless
AndersonWard
5 / 5 (1) Oct 23, 2012
Has anyone got a link to their work, the 2 links at the end of the article have thus far proved useless


Here is the paper:
arxiv.org/pdf/1208.0526v1.pdf