Gary McGuire

will speak on

Sudoku needs at least 17 clues

Time: 4:00PM
Date: Mon 27th February 2012
Location: CASL Seminar Room - Belfield Office Park [map]

Further information

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 and Number Theory series.)

PDF notice

Return to all seminars