1 Search Results for "Fujito, Toshihiro"


Document
The Fewest Clues Problem of Picross 3D

Authors: Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{kimura_et_al:LIPIcs.FUN.2018.25,
  author =	{Kimura, Kei and Kamehashi, Takuya and Fujito, Toshihiro},
  title =	{{The Fewest Clues Problem of Picross 3D}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.25},
  URN =		{urn:nbn:de:0030-drops-88168},
  doi =		{10.4230/LIPIcs.FUN.2018.25},
  annote =	{Keywords: Puzzle, computational complexity, fewest clues problem}
}
  • Refine by Author
  • 1 Fujito, Toshihiro
  • 1 Kamehashi, Takuya
  • 1 Kimura, Kei

  • Refine by Classification
  • 1 Theory of computation → Theory and algorithms for application domains

  • Refine by Keyword
  • 1 Puzzle
  • 1 computational complexity
  • 1 fewest clues problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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