Stronger hardness results on the computational complexity of picross 3D

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Picross 3D is a popular single-player puzzle video game for the Nintendo DS. It presents a rectangular parallelepiped (i.e., rectangular box) made of unit cubes, some of which must be removed to construct an object 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 object is complete. Kusano et al. showed that Picross 3D is NP-complete and Kimura et al. showed that the counting version, the another solution problem, and the fewest clues problem of Picross 3D are #P-complete, NP-complete, and ΣP 2-complete, respectively, where those results are shown for the restricted input that the rectangular parallelepiped is of height four. On the other hand, Igarashi showed that Picross 3D is NPcomplete even if the height of the input rectangular parallelepiped is one. Extending the result by Igarashi, we in this paper show that the counting version, the another solution problem, and the fewest clues problem of Picross 3D are #P-complete, NP-complete, and ΣP 2 complete, respectively, even if the height of the input rectangular parallelepiped is one. Since the height of the rectangular parallelepiped of any instance of Picross 3D is at least one, our hardness results are best in terms of height.

Original languageEnglish
Pages (from-to)668-676
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE103A
Issue number4
DOIs
Publication statusPublished - 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Stronger hardness results on the computational complexity of picross 3D'. Together they form a unique fingerprint.

Cite this