HackerPapers

arXiv:1201.0749cs.DS

There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem

Gary McGuire, Bastian Tugemann, Gilles Civario

Abstract

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.

arXiv comments
43 pages
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Jun 2017 to May 2023. Found in 2 HN submissions from Jan 2012 to Mar 2012. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Problems harder than NP-Complete 1 comment

    • Neat! More at https://www.technologyreview.com/2012/01/06/188520/mathemati... from when it was solved 10 years ago: > 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December. Though the…

      eesmithView on HNParent context

  2. Solving Sudoku with Prolog (2016) 1 comment

    • A valid Sudoku puzzle is such that the given clues admit precisely one solution. Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of…

      triskaView on HNParent context

  3. Let’s Publish Everything 1 comment

    • I believe that there is a misunderstanding regarding the role of academic publishing. Before the Internet era, the only way to make your work known to other scientists was to publish it in a journal—prestigious if possible. Journals were a medium to spread scientific information…

      noname120View on HNParent context

  4. Can Neural Networks Crack Sudoku? 1 comment

    • 9! * 9! is not the number of boards, that is a bad estimate. If you don't account for symmetries, rotations, re-numberings and other things, the number of boards is 6.7e21. Even if you could check a full board in a nanosecond (which you can't) enumerating that number would take…

      dahartView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.