2012/01/01 by Gary McGuire, McGuire, Gary, Bastian Tugemann +3 · 2 voices · 3 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1201.0749
43 pages
openalex publication_date 2012/01/01 · arxiv created 2013/09/01 · arxiv updated 2013/09/03 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The sudoku minimum number of clues problem is the following question: what is the smallest number of clues that a sudoku puzzle can have? For several years it had been conjectured that the answer is 17. We have performed an exhaustive computer search for 16-clue sudoku puzzles, and did not find any, thus proving that the answer is indeed 17. In this article we describe our method and the actual search. As a part of this project we developed a novel way for enumerating hitting sets. The hitting set problem is computationally hard; it is one of Karp's 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today's supercomputer speeds. To make an exhaustive search possible, we designed an algorithm that allowed us to efficiently enumerate hitting sets of a suitable size.