Herugolf and Makaro are NP-complete

Herugolf and Makaro are NP-complete
复制标题

DOI：
10.4230/lipics.fun.2018.24
复制
发表时间：
2018
期刊：
--
影响因子：
--
通讯作者：
Chuzo Iwamoto;Masato Haruishi;Tatsuaki Ibusuki
Chuzo Iwamoto;Masato Haruishi;Tatsuaki Ibusuki
中科院分区：
其他
文献类型：
--
作者：
Chuzo Iwamoto;Masato Haruishi;Tatsuaki Ibusuki

文献摘要

相似文献

Herugolf和Makaro是Nikoli的铅笔拼图。我们研究了Herugolf和Makaro问题的计算复杂性。它表明，决定是否一个给定的例子，每个难题有一个解决方案是NP完全的。
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.