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 October 21, 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 October 21, 2014).

Share This



More Computers & Math News

Tuesday, October 21, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Thanks, Marty McFly! Hoverboards Could Be Coming In 2015

Thanks, Marty McFly! Hoverboards Could Be Coming In 2015

Newsy (Oct. 21, 2014) — If you've ever watched "Back to the Future Part II" and wanted to get your hands on a hoverboard, well, you might soon be in luck. Video provided by Newsy
Powered by NewsLook.com
Robots to Fly Planes Where Humans Can't

Robots to Fly Planes Where Humans Can't

Reuters - Innovations Video Online (Oct. 21, 2014) — Researchers in South Korea are developing a robotic pilot that could potentially replace humans in the cockpit. Unlike drones and autopilot programs which are configured for specific aircraft, the robots' humanoid design will allow it to fly any type of plane with no additional sensors. Ben Gruber reports. Video provided by Reuters
Powered by NewsLook.com
Japanese Scientists Unveil Floating 3D Projection

Japanese Scientists Unveil Floating 3D Projection

Reuters - Innovations Video Online (Oct. 20, 2014) — Scientists in Tokyo have demonstrated what they say is the world's first 3D projection that floats in mid air. A laser that fires a pulse up to a thousand times a second superheats molecules in the air, creating a spark which can be guided to certain points in the air to shape what the human eye perceives as an image. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Apple Enters Mobile Payment Business

Apple Enters Mobile Payment Business

AP (Oct. 20, 2014) — Apple is making a strategic bet with the launch of Apple Pay, the mobile pay service aimed at turning your iPhone into your wallet. (Oct. 20) 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:

Strange & Offbeat Stories

 

Space & Time

Matter & Energy

Computers & Math

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