Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no hole. When all odd numbers are placed it is in P, whereas it is still NP-hard when all numbers of the form $3k+1$ are placed.
翻译：Rikudo 是一个设置数字的谜题, 玩家被要求在六边格中完成汉密尔顿语路径, 并给出一些线索( 数字已经放置, 路径边缘 ) 。 我们证明游戏对 NP 来说是完全的, 即使谜题没有洞。 当所有奇数被放置在 P 中时, 当所有窗体的数 3k+1$ 被放置时, 它仍然是 NP 硬的 。
相关内容
Arxiv
0+阅读 · 2021年3月17日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员