Document Open Access Logo

The Fewest Clues Problem of Picross 3D

Authors Kei Kimura, Takuya Kamehashi, Toshihiro Fujito

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.25.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Author Details

Kei Kimura
  • Department of Computer Science and Engineering, Toyohashi University of Technology, 1-1 Hibarigaoka, Tempaku, Toyohashi, Aichi, Japan
Takuya Kamehashi
  • Department of Computer Science and Engineering, Toyohashi University of Technology, 1-1 Hibarigaoka, Tempaku, Toyohashi, Aichi, Japan
Toshihiro Fujito
  • Department of Computer Science and Engineering, Toyohashi University of Technology, 1-1 Hibarigaoka, Tempaku, Toyohashi, Aichi, Japan

Funding

  • Kimura, Kei: The first author is supported by JSPS KAKENHI Grant Number JP15H06286.
  • Fujito, Toshihiro: The third author is supported by JSPS KAKENHI Grant Number JP17K00013.

Cite AsGet 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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  2. Nadia Creignou and Miki Hermann. On #P-completeness of some counting problems. Research report 2144, Institut de Recherche en Informatique et en Automatique, 1993. Google Scholar
  3. Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Information and Computation, 125:1-12, 1996. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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. Google Scholar
  7. Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A K Peters Ltd., 2009. Google Scholar
  8. Gabor T. Herman and Attila Kuba, editors. Discrete Tomography: Foundations, Algorithms, and Applications. Birkhäuser Basel, Pennsylvania, USA, 1999. Google Scholar
  9. Robert W. Irving and Mark R. Jerrum. Three-dimensional statistical data security problems. SIAM Journal on Computing, 23(1):170-184, 1994. Google Scholar
  10. 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). Google Scholar
  11. Brandon McPhail. Light up is NP-complete. Unpublished manuscript, 2005. URL: http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf.
  12. Takahiro Seta. The complexity of CROSS SUM. Sig technical reports, Information Processing Society of Japan, 2002 (in Japanese). Google Scholar
  13. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact