代码之家 › 专栏 › 技术社区 › Axarydax

如何编程解决15(移动数字)难题?

puzzle

Axarydax · 技术社区 · 14 年前

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15

我的女朋友或者我的一些非程序员朋友可以用一些他们无法向我解释的含糊不清的魔术来解决这个问题。我解不出这个谜。

我发现的最有希望的方法是先解第一行,然后得到

1   2  3  4
X   X  X  X
X   X  X  X
X   X  X

1   2  3  4
5   X  X  X
9   X  X  X
13  X  X

然后第二排到

1   2  3  4
5   6  7  8
9   X  X  X
13  X  X

然后是第二列

1   2  3  4
5   6  7  8
9   10  X  X
13  14  X

问题是,剩余的X(随机)块有时处于无法解决的位置,这就是我的解决方案失败的地方。但我觉得我走的路是对的。

如果可能的话,我的程序在不弄乱正确单元格的情况下,通过尝试将数字X移到指定的位置来解决指定的行/列。但它无法在2x2网格上完成最后3个平铺。我错过了什么?

7 回复 | 直到 7 年前

Rudu Andrew Whitaker 14 年前

你肯定是在正确的轨道上,但不是按行/列迭代求解到一个2x2的点,而是求解直到你有一个最小的3x3,然后只求解那个网格。3x3是正确重新订购网格所需的最小尺寸(而2x2并没有提供您可能需要的完全灵活性,正如您已经讨论过的)。这种方法也是可伸缩的-你可以解决5x5,10x10等。

John 14 年前

Not all are .

否则你的策略看起来很合理。

Oren A 14 年前

我认为解决这个问题最有效的方法是使用加法模式,加上一个合理的启发式算法和IDA*算法。如本文所述- http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf . (我想费尔纳告诉我们他找到了一个更好的方法,但我不记得确切的方法是什么(双向a*?),但无论如何,这应该是足够的(-:)。
无论如何,这门课是很久以前的事了,所以我建议你读这篇文章。。
嗯。当心。

GWW 14 年前

site 有一个很好的解释3x3网格,你可以很容易地扩展到4x4。

Jean-Bernard Pellerin 14 年前

通过简化,你不能解决的唯一可能的情况必须是
1 3
2 X
你想把它送到
1 2
3 X

通过使用额外的行和列,您可以用一个简单的预计算序列将它们移动到适当的位置

Josephine 14 年前

如果我们把拼图中的空白空间当作一个瓦片,那么每一个合法的动作都涉及为相邻的瓦片交换空白的“瓦片”。这使我们可以把拼图上的运动看作16个字符的排列。即对称群S的元素 ₁₆ . 每一个原始移动都是两个元素之间的“交换”或转置(其中一个是空白)。

₁₆ ,正好有一半的S ₁₆ . (16人中!S的排列 ₁₆ , 16!/2个排列是偶数,16个!/2个是奇数。此外,偶*偶=偶,偶*奇=奇,奇*奇=偶。)

如果必要的修正排列恰好是奇数,那么无论你做什么,都不可能解决这个难题。如果必要的校正排列是均匀的,并且如果Axarydax遵循所描述的策略,那么对于剩余的2x2块所需的排列必然是固定排列的空白方。只有三个元素的偶数排列是旋转1->2->3->1(循环表示法(123))和1->3->2->1(循环表示法(132))。在剩下的四个方格上很容易执行这些操作,而不会干扰其他方格。

Grozz 14 年前

从任何一个给定的移动位置总是有多达4个移动位置。我想知道这个简单的算法是否会覆盖构建2-4树的所有选项,从而到达“已解决”的位置或者堆栈溢出:)