Scientists make Sudoku puzzles easy to solve
For those who struggle to solve a Sudoku puzzle, scientists have come to your rescue! Researchers at University of Notre Dame have developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking.
October 12, 2012 / 21:24 IST
For those who struggle to solve a Sudoku puzzle, scientists have come to your rescue! Researchers at University of Notre Dame have developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking.
Researchers, Zoltan Toroczka and Maria Ercsey-Ravasz, however, cannot only explain why some Sudoku puzzles are harder than others. Toroczkai and Ercsey-Ravasz from Romanias Babes-Bolyai University, began studying Sudoku as part of their research into the theory of optimisation 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.They 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.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. Discover the latest Business News, Sensex, and Nifty updates. Obtain Personal Finance insights, tax queries, and expert opinions on Moneycontrol or download the Moneycontrol App to stay updated!
