Mathematician claims breakthrough in Sudoku puzzle

nature.com: Via: Mathematician claims breakthrough in Sudoku puzzle. Puzzles must have at least 17 clues to have a valid solution.

slashdot.org: Lower Limit Found For Sudoku Puzzle Clues

An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules.

Gary McGuire of University College Dublin shows in a proof posted online on 1 January1 that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.

“The approach is reasonable and it’s plausible. I’d say the attitude is one of cautious optimism,” says Jason Rosenhouse, a mathematician at James Madison University in Harrisonburg, Virginia, and the co-author of a newly released book on the maths of Sudoku.

Having spent two years testing the algorithm, McGuire and his team used about 700 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. “The only realistic way to do it was the brute force approach,” says Gordon Royle, a mathematician at the University of Western Australian in Perth who had been working on the problem of counting 17 clue puzzles using different algorithms.

Papier en format PDF

3 thoughts on “Mathematician claims breakthrough in Sudoku puzzle

  1. Interessant. Je me demande combien de temps ca prendrait pour verifier leurs calculs sur Colosse. Je pourrais demander a un etudiant de faire ca cet ete. 😉

  2. J’ai une idée: faire ton étudiant faire une sorte de “seti@home” undercover: une page web que t’installes sur ton serveur, avec un script javascript qui se lance sur la machine du visiteur au moment du chargement de la page; ce script calcule une série de vérifications de puzzle et se connecte avec le résultat encodé dans un query-url de retour à ton serveur. Le tout sans que le visiteur se doute. Tout ce qui reste c’est d’attirer assez de visiteurs sur ta page.

    LOL.

    Je me demande si google ne fait pas déjà qqchose comme cela.

  3. J’avoue qu’il doit y avoir du monde qui y ont deja pense. Mais le fait que javascript est tres lent et que le code source soit visible du point de vue du visiteur a du ralentir les ardeurs des developpeurs. Ceci etant dit, ca serait une excellente facon d’approcher ce genre de probleme.

Leave a Reply

Your email address will not be published. Required fields are marked *