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 July 26, 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 26, 2014).

Share This




More Computers & Math News

Saturday, July 26, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Mobile App Gives Tour of Battle of Atlanta Sites

Mobile App Gives Tour of Battle of Atlanta Sites

AP (July 25, 2014) — Emory University's Center for Digital Scholarship has launched a self-guided mobile tour app to coincide with the 150th anniversary of the Civil War's Battle of Atlanta. (July 25) Video provided by AP
Powered by NewsLook.com
Bill Gates: Health, Agriculture Key to Africa's Development

Bill Gates: Health, Agriculture Key to Africa's Development

AFP (July 24, 2014) — Health and agriculture development are key if African countries are to overcome poverty and grow, US software billionaire Bill Gates said Thursday, as he received an honourary degree in Ethiopia. Duration: 00:36 Video provided by AFP
Powered by NewsLook.com
Creative Makeovers for Ugly Cellphone Towers

Creative Makeovers for Ugly Cellphone Towers

AP (July 24, 2014) — Mobile phone companies and communities across the country are going to new lengths to disguise those unsightly cellphone towers. From a church bell tower to a flagpole, even a pencil, some towers are trying to make a point. (July 24) Video provided by AP
Powered by NewsLook.com
Robot Parking Valet Creates Stress-Free Travel

Robot Parking Valet Creates Stress-Free Travel

AP (July 23, 2014) — 'Ray' the robotic parking valet at Dusseldorf Airport in Germany lets travelers to avoid the hassle of finding a parking spot before heading to the check-in desk. (July 23) Video provided by AP
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