Boffin writes code to crack sudoku

How many times have you felt like a genius after filling in a number in the last of those vacant boxes but have cursed nobody in particular again and again for not getting it right?

A US mathematician says he has found a way to put an end to your agony. He has come up with a foolproof formula to solve sudoku, USA Today said on Monday.

JF Crook, a computer scientist at Winthrop University here, has written in the latest Notices of the American Mathematical Society that he has come up with the first guaranteed system, an algorithm, for solving the popular puzzle first introduced in London's The Times in 2004.

“The algorithm is a tree-based search algorithm based on backtracking in a tree until a solution is found,” Crook wrote in his paper— published at ams.com.

But even after using his method, there may be two possibilities for a particular box, Crook says. The player would have to guess which one is right and then repeat the steps to see if they lead to a solution. If the first guess doesn't work, erase and try the other option, says Crook.

“Sudoku has become the passion of many people the world over,” Crook wrote. “The interesting fact about sudoku is that it is a trivial puzzle to solve.”

“[But] Sudoku requires a kind of maths sense,” mathematician M Ram Murty of Canada's Queen's University in Kingston told the paper.

A sudoku puzzle has 81 squares, aligned in nine rows and nine columns, further broken up into 3x3 squares. Players have to fill in the blank squares with numbers between 1 and 9 without repeating any numbers in a row, column, or the nine interior 3x3 boxes of the puzzle.