The fewest clues problem of Picross 3D

DOI10.4230/LIPICS.FUN.2018.25zbMATH Open1489.68110OpenAlexW2810364690MaRDI QIDQ3301015FDOQ3301015

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/

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

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)

Cites Work

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

Cited In (1)

• Computational complexity of three-dimensional discrete tomography with missing data

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)