The fewest clues problem

DOI10.1016/J.TCS.2018.01.020MaRDI QIDQ1623268zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson

Publication date 23 November 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1721.1/123865

zbMATH Keywords

computational complexityhardness reductionspencil-and-paper puzzles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Recommendations

• The fewest clues problem
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Minimal number of clues for Sudokus
• The fewest clues problem of Picross 3D
• Computational complexity of NURIKABE

Cites work

• scientific article; zbMATH DE number 152108 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• PP is as Hard as the Polynomial-Time Hierarchy
• Planar Formulae and Their Uses
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The NP-Completeness of Some Edge-Partition Problems
• The complexity of completing partial Latin squares
• The complexity of computing the permanent

Cited in

(6)

• The fewest clues problem of Picross 3D
• Minimal number of clues for Sudokus
• On a complex KenKen problem
• Finding a unique solution to Radon-Kaczmarz puzzles
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• The fewest clues problem

This page was built for publication: The fewest clues problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623268)