HIROIMONO Is NP-Complete
HIROIMONO Is NP-Complete
复制标题
HIROIMONO 是 NP 完全的
DOI：
10.1007/978-3-540-72914-3_5
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Daniel Andersson
中科院分区：
文献类型：
--
作者：
Daniel Andersson
在Hiroimono谜题中，玩家必须从一个正方形网格中收集一组石头，沿着网格线沿着移动，当遇到石头时捡起它们，只有当捡起石头时才改变方向。我们表明，决定这样的难题的可解性是NP-完全的。
In a Hiroimono puzzle, one must collect a set of stones from a square grid, moving along grid lines, picking up stones as one encounters them, and changing direction only when one picks up a stone. We show that deciding the solvability of such puzzles isNP-complete.