Hidoku NP完成了吗？

Question

Hidoku是一个$ n times n $网格，一些预填充整数从1到$ n^2 $。目的是在网格中找到连续整数的路径（从1到$ n^2 $）。更具体地，网格的每个单元格必须包含一个不同的整数，从1到$ n^2 $，每个具有值$ z≠n^{2} $的单元格必须具有一个具有值$ z + 1 $的邻居单元格（还可以对角线）。

NP难以确定给定的Hidoku是否可以解决？可以使用什么减少？

编辑：根据评论，我给出一点澄清。给定的是单元格的网格，其中一些已经包含值（整数从1到N²）。我们必须使用从1到$ n^2 $的整数填充所有剩余的单元格，以便没有两个单元格具有相同的值，并且每个具有值$ z≠n²$的单元格都有一个具有值$ z + 1 $的邻居。也就是说，在填写单元格之后，我们必须找到路径$ 1、2、3， cdots，n^2 $。在逻辑上访问每个单元格的网格中。

Hidoku Woud的一个例子 http://www.janko.at/raetsel/hidoku/018.c.gif。已经解决的Hidoku是 http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_schwer_loesung_loesung_loesung20100810172340.gif, ，您可以看到我所指的路径。

Answer 1

我认为这是$ sf {np} $ - 完整：正如拉斐尔（Raphael 有孔 问题是np complete（Alon Itai，Christos H. Papadimitriou，Jayme Luiz Szwarcfiter：网格图中的汉密尔顿路径。 Siam J. Comput。 11（4）：676-686（1982）).

因此，考虑到带有孔的网格图$ g $，您可以轻松地构建等效的Hidoku游戏，其中最初的固定单元格填充了所有均匀的对角线；空的奇数对角线形成了一个无方向的图，该图等效于原始网格图$ g $，而Hidoku具有解决方案，并且仅当原始网格图具有Hamiltonian路径时。

图1：带有孔的网格图和等效的$ 12 times 12 $ hidoku拼图（蓝细胞代表初始固定编号的单元格（$ 1 $是第一个，$ 144 $是最后一个），白色单元是玩家必须的单元格填充，紫色线表示初始固定编号单元的序列）。

辅助（填充）线可以添加到底部或右侧，使其成为正方形。

从网格图还原为Hidoku难题的另一个例子：6x4网格图嵌入在较大的13x13网格中；均匀的对角线充满固定数字，其余的游离单元格等于原始网格图。

完整的转换图 可以在这里下载.

一些其他注释来完成答案：

• 这个问题也称为 HIDATO;董事会可以具有任意形状（但作为方案的概括，它仍然是np-hard）；

• 正如史蒂文·斯塔德尼奇（Steven Stadnicki）在他的回答中正确证明的那样，如果最初的部分填充的网格没有作为$ n times n $ n $整数阵列，则问题在NP中并不明显。 简洁 表示;但是，如果使用该初始板，则显然是在NP中 合理的 整数表示列表；

• 我认为游戏的原始规则说 解决方案应该是唯一的;所以问题在 我们 （美国 - hard），不太可能出现在NP中。

总而言之，如果我们删除唯一的解决方案约束并用$ n^2 $整数列表指定初始板，则游戏为$ sf {np} $ - 完成。

Answer 2

一个微妙的捕捉：虽然我认为VOR的答案在解释为什么会很难的情况下做得很好，但目前尚不清楚问题是 在 NP，取决于您定义的输入大小！请注意，$ n times n $网格的问题规范实际上并不一定是$ omega（n）$的尺寸；它由整数$ n $（尺寸$ lg n $）和一些数量的整数$（x_i，y_i，w_i）组成：x_i，y_i leq n，w_i w_i leq n^2 $说，带有坐标的单元$（x_i，y_i）$具有值$ w_i $;这些三胞胎中的每一个都是$ lg n + lg n + lg n^2 = 4 lg n in O（ lg n）$，因此，除非您至少有$ omega（n）$ treelets指定的初始值，那么您的总输入大小实际上可能是$ o（n）$。

您可能至少需要至少需要$ omega（n）$具有独特的解决方案，因此任何小于许多givens的规范都可以拒绝，但是（a）您要问的是关于问题的“唯一解决方案”变体，而不是“存在解决方案”变体，并且（b）也不是立即明显的，即使该限制是正确的；我不确定如何尝试证明这一点。

（有关类似问题的讨论，请参阅我的问题 简洁的Nurikabe的复杂性 在csthory.se网站上。