## Featured Research

from universities, journals, and other organizations

# Making Sudoku puzzles less puzzling

Date:
October 11, 2012
Source:
University of Notre Dame
Summary:
For anyone who has ever struggled while attempting to solve a Sudoku puzzle, mathematicians are coming 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.

For anyone who has ever struggled while attempting to solve a Sudoku puzzle, University of Notre Dame complex networks researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravasz are coming to the rescue.
Credit: © Jiri Hera / Fotolia

For anyone who has ever struggled while attempting to solve a Sudoku puzzle, University of Notre Dame complex networks researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravasz are coming 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 Ercsey-Ravasz, of Romania's Babeş-Bolyai University, began studying Sudoku as part of their research into the theory of optimization and computational complexity. They note that most Sudoku enthusiasts 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 Sudoku puzzle until the correct answer is found. While the method is successful, it is also time consuming.

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

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 believe their analog algorithm potentially can 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 and Ercsey-Ravasz'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.

Story Source:

The above story is based on materials provided by University of Notre Dame. The original article was written by William G. Gilroy. Note: Materials may be edited for content and length.

Journal References:

1. Mária Ercsey-Ravasz, Zoltán Toroczkai. Optimization hardness as transient chaos in an analog approach to constraint satisfaction. Nature Physics, 2011; 7 (12): 966 DOI: 10.1038/nphys2105
2. Mária Ercsey-Ravasz, Zoltán Toroczkai. The Chaos Within Sudoku. Scientific Reports, 2012; 2 DOI: 10.1038/srep00725

University of Notre Dame. "Making Sudoku puzzles less puzzling." ScienceDaily. ScienceDaily, 11 October 2012. <www.sciencedaily.com/releases/2012/10/121011151627.htm>.
University of Notre Dame. (2012, October 11). Making Sudoku puzzles less puzzling. ScienceDaily. Retrieved July 23, 2014 from www.sciencedaily.com/releases/2012/10/121011151627.htm
University of Notre Dame. "Making Sudoku puzzles less puzzling." ScienceDaily. www.sciencedaily.com/releases/2012/10/121011151627.htm (accessed July 23, 2014).

## More Computers & Math News

Wednesday, July 23, 2014

### Featured Research

from universities, journals, and other organizations

### Featured Videos

from AP, Reuters, AFP, and other news services

Google Plans To Speed Up Web Pages With New Image Format

### Google Plans To Speed Up Web Pages With New Image Format

Newsy (July 21, 2014) — Google is using compressed images in WebP format to help boost page loading times. The files are 25-to-34 percent smaller than PNGs and JPEGs. Video provided by Newsy
Uruguayan Creates Chess Game for Multiple Opponents

### Uruguayan Creates Chess Game for Multiple Opponents

AFP (July 19, 2014) — It no longer takes two to play chess – or at least according to a new version of the game invented by Uruguayan Gabriel Baldi, where up to four opponents can play. Duration: 00:31 Video provided by AFP
Clock Ticks Down on Internet Speed Debate

### Clock Ticks Down on Internet Speed Debate

Reuters - US Online Video (July 18, 2014) — The FCC received more than 800,000 comments on whether and how internet speeds should be regulated, even crashing its system. Lily Jamali reports. Video provided by Reuters

Newsy (July 18, 2014) — The European Commission asked Google and Apple not to label apps "free" if they include in-app purchases. Google has complied; Apple has resisted. Video provided by Newsy

## Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):

Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

## In Other News

... from NewsDaily.com

Save/Print:
Share:

## Free Subscriptions

Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

## Get Social & Mobile

Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

## Have Feedback?

Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web