1 Search Results for "Ibusuki, Tatsuaki"


Document
Herugolf and Makaro are NP-complete

Authors: Chuzo Iwamoto, Masato Haruishi, and Tatsuaki Ibusuki

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


Abstract
Herugolf and Makaro are Nikoli's pencil puzzles. We study the computational complexity of Herugolf and Makaro puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.

Cite as

Chuzo Iwamoto, Masato Haruishi, and Tatsuaki Ibusuki. Herugolf and Makaro are NP-complete. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{iwamoto_et_al:LIPIcs.FUN.2018.24,
  author =	{Iwamoto, Chuzo and Haruishi, Masato and Ibusuki, Tatsuaki},
  title =	{{Herugolf and Makaro are NP-complete}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{24:1--24:11},
  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.24},
  URN =		{urn:nbn:de:0030-drops-88159},
  doi =		{10.4230/LIPIcs.FUN.2018.24},
  annote =	{Keywords: Herugolf, Makaro, pencil puzzle, NP-complete}
}
  • Refine by Author
  • 1 Haruishi, Masato
  • 1 Ibusuki, Tatsuaki
  • 1 Iwamoto, Chuzo

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Herugolf
  • 1 Makaro
  • 1 NP-complete
  • 1 pencil puzzle

  • 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