LIPIcs.FUN.2018.25.pdf
- Filesize: 0.6 MB
- 13 pages
Document
The Fewest Clues Problem of Picross 3D
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito. The Fewest Clues Problem of Picross 3D. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FUN.2018.25
Abstract
Picross 3D is a popular single-player puzzle video game for the Nintendo DS. It is a 3D variant of Nonogram, which is a popular pencil-and-paper puzzle. While Nonogram provides a rectangular grid of squares that must be filled in to create a picture, Picross 3D presents a rectangular parallelepiped (i.e., rectangular box) made of unit cubes, some of which must be removed to construct an image in three dimensions. Each row or column has at most one integer on it, and the integer indicates how many cubes in the corresponding 1D slice remain when the image is complete. It is shown by Kusano et al. that Picross 3D is NP-complete. We in this paper show that the fewest clues problem of Picross 3D is Sigma_2^P-complete and that the counting version and the another solution problem of Picross 3D are #P-complete and NP-complete, respectively.
Subject Classification
ACM Subject Classification
- Theory of computation → Theory and algorithms for application domains
Keywords
- Puzzle
- computational complexity
- fewest clues problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
-
Nadia Creignou and Miki Hermann. On #P-completeness of some counting problems. Research report 2144, Institut de Recherche en Informatique et en Automatique, 1993.
-
Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125:1-12, 1996.
-
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, and Scott Aaronson. The fewest clues problem. In Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), volume 49 of LIPIcs, pages 12:1-12:12, 2016.
-
Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno. Computational complexity and an integer programming model of shakashaka. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 97:1213-1219, 2014.
-
R. J. Gardner, P. Gritzmann, and D. Prangenberg. On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Mathematics, 202:45-71, 1999.
-
Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters Ltd., 2009.
-
Gabor T. Herman and Attila Kuba, editors. Discrete Tomography: Foundations, Algorithms, and Applications. Birkhäuser Basel, Pennsylvania, USA, 1999.
-
Robert W. Irving and Mark R. Jerrum. Three-dimensional statistical data security problems. SIAM Journal on Computing, 23(1):170-184, 1994.
-
Kazuhiko Kusano, Kazuyuki Narisawa, and Ayumi Shinohara. Picross 3D is NP-complete. In Proceedings of the 15th Game Programming Workshop 2010, pages 108-113, 2010 (in Japanese).
- Brandon McPhail. Light up is NP-complete. Unpublished manuscript, 2005. URL: http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf.
-
Takahiro Seta. The complexity of CROSS SUM. Sig technical reports, Information Processing Society of Japan, 2002 (in Japanese).
-
Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 86:1052-1060, 2003.