# Researchers make Sudoku puzzles less puzzling

##### Oct 11, 2012

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: Researchers use Twitter to predict crime

## Related Stories

#### Mathematicians use computer to solve minimum Sudoku solution problem

Jan 06, 2012

(PhysOrg.com) -- Over the past several years, Sudoku, as most people know, has become wildly popular. Where once mainstream newspapers carried only crossword puzzles, they now also carry a Sudoku puzzle as ...

#### 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.

#### Physicists propose solution to constraint satisfaction problems

Oct 10, 2011

(PhysOrg.com) -- Maria Ercsey-Ravasz, a postdoctoral associate and Zoltan Toroczkai, professor of physics at the University of Notre Dame, have proposed an alternative approach to solving difficult constraint ...

#### Physicist's algorithm simplifies biological imaging -- and also solves Sudoku puzzles

Mar 02, 2006

Cornell physicist Veit Elser has been engrossed recently in resolving a pivotal question in biological imaging. So he hasn't had much time for brainteasers and number games.

#### 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

#### Researchers use Twitter to predict crime

8 hours ago

Hidden in the Twittersphere are nuggets of information that could prove useful to crime fighters—even before a crime has been committed.

#### UT Dallas professor to develop framework to protect computers' cores

Apr 18, 2014

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

Apr 18, 2014

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

Apr 18, 2014

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

##### 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

## More news stories

#### Google Trends info is placed on inbox duty for subscribers

(Phys.org) —Google Trends has added a new service to its mix, where users can enter email subscriptions for Google Trends, and can be sent notifications on topics of interest, showing them what is popular ...

#### Nintendo's trailblazing Game Boy marks 25th anniversary

Nintendo's trailblazing Game Boy marks its 25th anniversary on Monday with the portable device's legacy living on in cutting-edge smartphone games and among legions of nostalgic fans.

#### Hackers of Oman news agency target Bouteflika

Hackers on Sunday targeted the website of Oman's official news agency, singling out and mocking Algeria's newly re-elected president Abdelaziz Bouteflika as a handicapped "dictator".

#### Researchers use Twitter to predict crime

Hidden in the Twittersphere are nuggets of information that could prove useful to crime fighters—even before a crime has been committed.

#### Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

#### Study casts doubt on climate benefit of biofuels from corn residue

Using corn crop residue to make ethanol and other biofuels reduces soil carbon and can generate more greenhouse gases than gasoline, according to a study published today in the journal Nature Climate Change.

#### Bulletproof nuclei? Stem cells exhibit unusual absorption property

Stem cells – the body's master cells – demonstrate a bizarre property never before seen at a cellular level, according to a study published today from scientists at the University of Cambridge. The property ...

#### 'Chaperone' compounds offer new approach to Alzheimer's treatment

A team of researchers from Columbia University Medical Center (CUMC), Weill Cornell Medical College, and Brandeis University has devised a wholly new approach to the treatment of Alzheimer's disease involving ...

#### Team identifies source of most cases of invasive bladder cancer

A single type of cell in the lining of the bladder is responsible for most cases of invasive bladder cancer, according to researchers at the Stanford University School of Medicine.

#### Researchers uncover link between Down syndrome and leukemia

Although doctors have long known that people with Down syndrome have a heightened risk of developing acute lymphoblastic leukemia (ALL) during childhood, they haven't been able to explain why. Now, a team ...