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

Cite This Page:

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 August 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 August 23, 2014).

Share This




More Computers & Math News

Saturday, August 23, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Apple iPhone 6 Screen Hits Snag Ahead of Launch

Apple iPhone 6 Screen Hits Snag Ahead of Launch

Reuters - Business Video Online (Aug. 22, 2014) — Reuters has learned Apple is scrambling to get enough screens ready for the iPhone 6. Sources say it's unclear whether this could delay the launch. Fred Katayama reports. Video provided by Reuters
Powered by NewsLook.com
Is Apple's iMessage Really Being Overrun By Spammers?

Is Apple's iMessage Really Being Overrun By Spammers?

Newsy (Aug. 21, 2014) — A report says more than one third of all SMS spam over the past year came from a "single campaign" using iMessage and targeting iPhone users. Video provided by Newsy
Powered by NewsLook.com
Families Can Now Ask Twitter To Remove Photos Of Deceased

Families Can Now Ask Twitter To Remove Photos Of Deceased

Newsy (Aug. 20, 2014) — In the wake of a high-profile harassment case, Twitter says family members can ask for photos of dying or dead relatives to be taken down. Video provided by Newsy
Powered by NewsLook.com
Ballmer Leaves Microsoft's Board, Has Advice For Nadella

Ballmer Leaves Microsoft's Board, Has Advice For Nadella

Newsy (Aug. 19, 2014) — In a letter to Microsoft CEO Satya Nadella, Ballmer said he's leaving the board of directors and offered tips on how the company can be successful. Video provided by Newsy
Powered by NewsLook.com

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

Science News

Health News

Environment News

Technology News



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
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins