2026-08-07T23:59:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8815 2024-03-06T10:42:43Z ddc:004 open_access

Herugolf and Makaro are NP-complete Iwamoto, Chuzo Haruishi, Masato Ibusuki, Tatsuaki Herugolf Makaro pencil puzzle NP-complete 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chuzo Iwamoto and Masato Haruishi and Tatsuaki Ibusuki 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.24 urn:nbn:de:0030-drops-88159 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode