TY - GEN
T1 - The fewest clues problem of picross 3D
AU - Kimura, Kei
AU - Kamehashi, Takuya
AU - Fujito, Toshihiro
N1 - Publisher Copyright:
© Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito; licensed under Creative Commons License CC-BY 9th International Conference on Fun with Algorithms (FUN 2018).
PY - 2018/6/1
Y1 - 2018/6/1
N2 - 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 ΣP 2 -complete and that the counting version and the another solution problem of Picross 3D are #P-complete and NP-complete, respectively.
AB - 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 ΣP 2 -complete and that the counting version and the another solution problem of Picross 3D are #P-complete and NP-complete, respectively.
UR - http://www.scopus.com/inward/record.url?scp=85048950116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048950116&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FUN.2018.25
DO - 10.4230/LIPIcs.FUN.2018.25
M3 - Conference contribution
AN - SCOPUS:85048950116
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 251
EP - 2513
BT - 9th International Conference on Fun with Algorithms, FUN 2018
A2 - Prencipe, Giuseppe
A2 - Ito, Hiro
A2 - Leonardi, Stefano
A2 - Pagli, Linda
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 9th International Conference on Fun with Algorithms, FUN 2018
Y2 - 13 June 2018 through 15 June 2018
ER -