logo标签列表

如何通过编程解决15数码游戏（移动数字）难题？

puzzle
14

大家可能都见过移动数字/图片拼图游戏。这个游戏中，你需要在一个4x4的网格中移动1到15的数字，将它们从随机的起始位置移动到

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个方块。我错过了什么？

感谢所有的回复！ - Axarydax
1
感谢您发布这种方法。我为iOS开发了一个滑块拼图应用程序，并在解决4x4滑块拼图方面遇到了挑战。我采用了这种方法，并在314步内解决了它。 - Jason TEPOORTEN
7个回答
10
1
非常有趣，但我肯定他的原始算法仍然可能在可解的数字顺序上失败。 - userx
用户X：你有参考资料吗？我很想看看。你认为他的算法哪一部分可能会失败？我唯一能想到可能失败的部分是解决最后的2x3块，但似乎不太可能。唯一的诀窍就是将左边的两个拼图放在正确的位置（例如标准4x4上的10和14）。此时，剩下的三个拼图要么被正确排序，要么没有。然后，问题又回到了原始拼图是否可解的问题上。 - John
如何确定谜题是否可解？ - IgorGanapolsky
6
你肯定走在正确的道路上，但不要通过逐行/逐列迭代解决问题，直到只剩下一个2x2的格子，而是要解决至少3x3的矩阵，然后再解决那个矩阵。 3x3是你需要的最小尺寸，以正确重新排序网格（而2x2不会给你完全的灵活性，正如你已经讨论过的那样）。这种方法也是可扩展的-你可以解决5x5、10x10等等。
我一直认为3×2是最小的灵活尺寸，而不是3×3。 - Roland Illig
最小的灵活尺寸是3×2还是3×3？ - Axarydax
4
我认为解决这个问题最有效的方法是使用可接受启发式和IDA*算法进行添加模式。如此文献所述 - http://www.aaai.org/Papers/JAIR/Vol22/JAIR-2209.pdf。（我想Felner告诉我们他找到了一种更好的方法，但我不记得具体是什么（双向A*？）。总之，这应该足够了（-:）
无论如何，这门课程很久以前了，所以我建议阅读这篇文章...
希望对你有所帮助。注意安全。
3
这个网站对3x3的网格有很好的解释，你可以很容易地将其扩展到4x4。
针对3x3的解决方案并不适用于每种情况下的更大尺寸。 - nologin
1
通过简化，您无法解决的唯一可能情况必须是以下形式：
1 3
2 X
并且您希望将其转换为
1 2
3 X 通过使用附加行和列，您可以使用简单预先计算的序列将它们移动到正确的位置。
1

原帖中描述的解决策略对于标准可解的15数码难题总是有效的。如果Axarydax能够将15数码难题缩减到他所描述的状态，但仍然无法解决它，那么这个问题本来就是不可能解决的。让我来解释一下。

如果我们将拼图中的空格视为其中一个方块，则每个合法移动都涉及将该空白“方块”与相邻的方块交换。这使我们可以将拼图上的动作视为16个字符的置换。也就是说，对称群S16的元素。每个基本移动都是仅涉及两个元素（其中之一是空白）的“交换”或置换。

因为拼图从右下角的空白块开始并结束，所以空白块必须移动偶数次才能解决拼图问题。（最容易看到这一点的方法是在拼图上方想象一个重叠的棋盘格图案--经过奇数次移动后，空白块将位于不同颜色的方格上。）这意味着实施的解决方案必须是偶数排列的乘积，因此它必须是交错群A16的元素，该群恰好有S16的一半。（在S16的16!个排列中，有16!/2个排列是偶数的，16!/2个排列是奇数的。此外，偶数*偶数=偶数，偶数*奇数=奇数，奇数*奇数=偶数。）

如果必要的修正置换是奇数，那么无论你做什么都无法解决这个难题。如果必要的修正置换是偶数，并且Axarydax遵循所描述的策略，那么剩余的2x2块所需的置换将必然是一个固定空白方块的偶置换。只有三个元素的偶排列是旋转1->2->3->1（循环表示法（123））和1->3->2->1（循环表示法（132））。这些操作可以轻松地在其余四个方块上执行而不会干扰其他方块。
由于Axarydax无法理解这些2x2块的微不足道的解决方案是不可信的，我怀疑他/她要么被恶作剧了，要么正在尝试非标准的15拼图。
0

从任何给定的位置，始终存在最多4个移动位置。我想知道是否简单的遍历所有选项并构建2-4树的算法将达到“解决”位置或堆栈溢出 :)

我不需要那么复杂的东西，我已经有一个简单的算法来尝试解决它，例如“找到数字1并将其移动到左上角”，“找到数字2并将其移动到其位置，将3和4放在一起并将它们移动到完成第一行”。但问题出现在最后的2x3或3x3块。 - Axarydax
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接