Computational Complexity of Herugolf and Makaro

Chuzo IWAMOTO  Masato HARUISHI  Tatsuaki IBUSUKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1118-1125
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1118
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Puzzles
Keyword: 
Herugolf,  Makaro,  pencil puzzle,  NP-complete,  

Full Text: PDF(1.4MB)>>
Buy this Article




Summary: 
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.