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, ,您可以看到我所指的路径。

有帮助吗?

解决方案

我认为这是$ 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路径时。

enter image description here

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

辅助(填充)线可以添加到底部或右侧,使其成为正方形。

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

enter image description here

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

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

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

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

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

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

其他提示

一个微妙的捕捉:虽然我认为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网站上。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top