## 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 language | English |
---|---|

Pages (from-to) | 668-676 |

Number of pages | 9 |

Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |

Volume | E103A |

Issue number | 4 |

DOIs | |

Publication status | Published - 2020 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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