
Mathematicians come up with formula to complete every Sudoku
http://www.dailymail.co.uk/sciencetech/article2216642/ProblemsolvedsortMathematicians
comeformulacompleteSudokutryingunderstandlongerdoingpuzzle.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 copout.
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 ErcseyRavasz, from the University of Notre Dame also say they can also explain why some puzzles are harder than others.
Toroczkai and ErcseyRavasz, who also studies at Romania's BabesBolyai 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 NPcomplete problem) The algorithm given by Toroczkai and ErcseyRavasz does not get around this fundamental limitation, as it comes with no guarantees of efficiency.
Posted by
Răzvan Florian
14/10/12
