Herugolf and Makaro are NP-complete

Authors Chuzo Iwamoto, Masato Haruishi, Tatsuaki Ibusuki



PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.24.pdf
  • Filesize: 0.51 MB
  • 11 pages

Document Identifiers

Author Details

Chuzo Iwamoto
  • Hiroshima University, Graduate School of Engineering, Higashi-Hiroshima 739-8527, Japan
Masato Haruishi
  • Hiroshima University, Graduate School of Engineering, Higashi-Hiroshima 739-8527, Japan
Tatsuaki Ibusuki
  • Hiroshima University, School of Integrated Arts and Sciences, Higashi-Hiroshima 739-8521, Japan

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.FUN.2018.24

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Herugolf
  • Makaro
  • pencil puzzle
  • NP-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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