Sudoku needs at least 17 clues
Speaker: Gary McGuire
Time: 4:00PM
Date: Mon 27th February 2012
Location: CASL Seminar Room - Belfield Office Park
Abstract
The {\em Sudoku minimum number of clues problem\/} is the following question: What is the smallest number of clues (givens) that a Sudoku puzzle may have? It was conjectured that the answer is 17. We have performed an exhaustive search for a 16-clue Sudoku puzzle, and we did not find one, thereby proving that the answer is indeed 17. This talk describes our method and the actual search.
The biggest hurdle in this project was to find a better way to enumerate hitting sets. Recall that the Hitting Set Problem is computationally hard; in fact, it is one of Richard Karp's twenty-one classic NP-complete problems. Hitting set problems arise in many areas of science, such as bio-informatics and software testing. We have designed a new algorithm that allows us to efficiently enumerate hitting sets of a suitable size.
(This talk is part of the Algebra/Claude Shannon Institute series.)
Social Media Links