Archive for NP-complete problem

Sudokus with minimum number of clues

Posted in Statistics, University life with tags , , on January 9, 2012 by xi'an

Yesterday, I spotted on a Spanish post on the minimal number of clues to solve a Sudoku in a unique way. The original paper was posted on arXiv on January 1, in the Data structure and algorithms category. The authors, Gary McGuire, Bastian Tugemann, and Gilles Civario from University College Dublin, have shown by an exhaustive search that no Sudoku with 16 clues exist (in the sense of having a unique solution). The actual computation actually tooks 7.1 million core hours on the Stokes machine, which is a cluster with 320 nodes, which represents about a year in real time! The Sudoku solver the authors used was Brian Turner’s open source solver. (Here is a review of solvers.) Very impressive…