Communications of the ACM
Notre Dame Researcher Helps Make Sudoku Puzzles Less Puzzling
A Sudoku puzzle.
Credit: University of Notre Dame
University of Notre Dame researchers have determined why some Sudoku puzzles are harder than others and developed an algorithm that solves them very quickly.
The researchers have proposed a universal analog algorithm that is completely deterministic and always arrives at the correct solution to a Sudoku problem, and does so more quickly. The researchers also discovered that the time it took to solve a problem with their algorithm correlated with the difficulty of the problem as rated by human solvers.
"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," says Notre Dame researcher Zoltan Toroczkai. "Our analog solver is deterministic--there are no random choices or backtracks made during the dynamics." The researchers say their algorithm could be applied to a wide variety of problems in industry, computer science, and computational biology.
From Notre Dame University
View Full Article
Abstracts Copyright © 2012 Information Inc., Bethesda, Maryland, USA
No entries found