# Researchers make Sudoku puzzles less puzzling

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

## Related Stories

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

March 2, 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.

#### Toy Robot to Solve Sudoku (w/ Video)

September 3, 2009

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

#### Discovery could lead to more difficult Sudoku puzzles

February 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 the way that ...

#### Physicists propose solution to constraint satisfaction problems

October 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 satisfaction ...

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

January 6, 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 well. But along ...

## Recommended for you

#### From allergens to anodes: Pollen derived battery electrodes

February 5, 2016

Pollens, the bane of allergy sufferers, could represent a boon for battery makers: Recent research has suggested their potential use as anodes in lithium-ion batteries.

#### Mapping website tells building owners if going solar is worth the cost of installation

February 5, 2016

Nations worldwide are increasingly embracing solar power as an alternative electricity source for homes, buildings, and even the grid. Since 2008, installed solar capacity in the United States alone has grown 17-fold, from ...

#### World's biggest wind farm given go-ahead off Britain

February 4, 2016

A wind farm that would be the largest in the world and power more than a million homes has been given the go-ahead in Britain.

#### World is embracing clean energy, professor says

February 1, 2016

Renewable, energy efficient and flexible electricity sources are being adopted by policy makers and investors across the globe and this is sign of optimism in the battle against climate change, a University of Exeter energy ...

#### Battery technology could charge up water desalination

February 4, 2016

The technology that charges batteries for electronic devices could provide fresh water from salty seas, says a new study by University of Illinois engineers. Electricity running through a salt water-filled battery draws the ...

#### Researchers find vulnerability in two-factor authentication

February 3, 2016

Two-factor authentication is a computer security measure used by major online service providers to protect the identify of users in the event of a password loss. The process is familiar: When a password is forgotten, the ...

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