Computational Complexity of Herugolf and Makaro
Chuzo IWAMOTO, Masato Haruishi, Tatsuaki Ibusuki · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2019
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.