There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration

DOI10.1080/10586458.2013.870056zbMath1296.05008arXiv1201.0749OpenAlexW2099112283WikidataQ92380716 ScholiaQ92380716MaRDI QIDQ2875538

Gilles Civario, Gary McGuire, Bastian Tugemann

Publication date: 8 August 2014

Published in: Experimental Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.0749

zbMATH Keywords

sudokuminimum number of cluescritical setshitting set problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Orthogonal arrays, Latin squares, Room squares (05B15)

Related Items (15)

A new algorithm for enumerating all possible Sudoku squares ⋮ Sudoku rectangle completion (extended abstract) ⋮ Unnamed Item ⋮ Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs ⋮ Critical sets for Sudoku and general graph colorings ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Sudoku number of graphs ⋮ What (Quilting) Circles Can Be Squared? ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ On a generalization of ``eight blocks to madness puzzle ⋮ DIVISION SUDOKUS: INVARIANTS, ENUMERATION, AND MULTIPLE PARTITIONS ⋮ Minimal number of clues for Sudokus ⋮ Quantum Mechanics and Global Determinism ⋮ Reducing the generalised Sudoku problem to the Hamiltonian cycle problem ⋮ On the number of Sudoku squares

Cites Work

• An efficient fixed-parameter algorithm for 3-hitting set
• The four-colour theorem
• Minimal number of clues for Sudokus
• A proof of the Kepler conjecture
• Kernelization Algorithms for d-Hitting Set Problems

This page was built for publication: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration