Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Mathematicians come up with formula to complete every Sudoku

http://www.dailymail.co.uk/sciencetech/article-2216642/Problem-solved--sort-Mathematicians
-come-formula-complete-Sudoku-trying-understand-longer-doing-puzzle.html


http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html

For those who enjoy the challenge of a hard Suduko puzzle it could be seen as something of cop-out.

But for those who find them too much of a struggle it could be, literally, just the solution.

Two researchers have developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking.

Complex networks researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravasz, from the University of Notre Dame also say they can also explain why some puzzles are harder than others.

Toroczkai and Ercsey-Ravasz, who also studies at Romania's Babes-Bolyai University, began analysing Sudoku as part of their research into the theory of optimisation and computational complexity.

NOTE: The title (coming from the first quoted press release) is somewhat misleading: Sudoku is a problem that CANNOT be solved efficiently in the general case (it is an NP-complete problem) The algorithm given by Toroczkai and Ercsey-Ravasz does not get around this fundamental limitation, as it comes with no guarantees of efficiency.

Posted by Răzvan Florian

14/10/12

   
© Ad Astra 2001-2013