The fewest clues problem of Picross 3D

DOI10.4230/LIPICS.FUN.2018.25MaRDI QIDQ3301015zbMATHOpenAlexFDO

Authors Kei Kimura, Takuya Kamehashi, Toshihiro Fujito

Publication date 11 August 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8816/pdf/LIPIcs-FUN-2018-25.pdf/

zbMATH Keywords

computational complexitypuzzlefewest clues problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Game theory (91A99)

Recommendations

• The fewest clues problem
• The fewest clues problem
• Path puzzles: discrete tomography with a path constraint is hard
• Nonograms: combinatorial questions and algorithms
• Shikaku and Ripple Effect are NP-complete

Cites work

• Complexity of generalized satisfiability counting problems
• Computational Complexity
• Discrete tomography. Foundations, algorithms, and applications
• Games, puzzles, and computation
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• The fewest clues problem
• Three-dimensional Statistical Data Security Problems

Cited in

(3)

• Computational complexity of three-dimensional discrete tomography with missing data
• The fewest clues problem
• The fewest clues problem

This page was built for publication: The fewest clues problem of Picross 3D

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