LIPIcs.FUN.2018.24.pdf
- Filesize: 0.51 MB
- 11 pages
Document
Herugolf and Makaro are NP-complete
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get 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)
0PDF Downloads