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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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
• Planar Formulae and Their Uses
• PP is as Hard as the Polynomial-Time Hierarchy
• The complexity of completing partial Latin squares
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(12)

• Minimal number of clues for Sudokus
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• The fewest clues problem of Picross 3D
• On a complex KenKen problem
• Finding a unique solution to Radon-Kaczmarz puzzles
• The fewest clues problem
• Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3
• All paths lead to Rome
• Tetris with few piece types
• How many clues to give? A bilevel formulation for the minimum Sudoku clue problem
• The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs
• Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

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)