London, October 12 (ANI): In a new study, researchers have not only explained why some Sudoku puzzles are harder than others but have also developed a mathematical algorithm that solves them very quickly and without any guessing or backtracking.
University of Notre Dame researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravaz 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-Ravaz have proposed a universal analogue 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 analogue 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 said.
The researchers feel that their analogue 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 said.
The study was first published in Nature Physics and its application to Sudoku appears in Nature Scientific Reports. (ANI)
