以编程方式解决魔方问题

Question

我正在尝试用C语言开发一个解决魔方的程序。我使用了回溯技术，但这是一个非常耗时的过程，并且需要很多迭代，所以我无法解决它。

请给我一些建议，告诉我如何更有效地解决这个问题-例如其他技术或采用回溯本身。在Google上我找到了很多快捷方式来解决这个问题，但我不想使用快捷方式来解决它。

- Aravindhan

---

“快捷方式”是什么意思？ - Oliver Charlesworth

请查看此链接：http://www.chessandpoker.com/rubiks-cube-solution.html，在这里他们将在5分钟内解决魔方。 - Aravindhan

你介意编辑一下你的问题，以更清晰地说明你目前的方法吗？我已经为了更清晰而编辑了你的问题。 - Tim Post

查看例如Hofstadter的《超魔幻主题》一书，以讨论魔方的数学属性。通过使用一些群论，您可以定义复杂的移动模式来交换两个方块，从而使您的搜索更加高效。 - Fred Foo

Answer 1

为什么不使用以人为本的解决方案并进行编程呢？需要一些模式匹配，但并不难。（此外还有程序可以解决1000x1000x1000的问题。）基本想法是分阶段工作：

第一层 第二层 第三层

对于每一层，您实现了几个算法，将模式X转换为模式X'。每个阶段中的每个步骤都应该使魔方接近解决。您可以通过为每个模式添加一个值（其中更多未解决的魔方给予更高的值）来实现这一点。您还可以添加难度（例如转数），因此可以根据每个难度的最佳价值增益选择算法（或以最少的转数达到最佳结果）。

这种方法的乐趣在于，您可以添加新的算法，并测试它们的使用频率。因此，您可以测试每个算法的有用性。

如果您真的想赚取那些极客积分，请创建一个单独的语言来描述算法和它们解决的模式。

- Toon Krijthe

---

对于更大的魔方，比逐层解决更好的方法是先解决中心，然后解决边缘，最后解决得到的3x3x3。 - hoang

@pranavk 这取决于DP的含义。 - Anderson Green

@AndersonGreen，下次我用迪士尼公主来解决魔方;-)。 - Toon Krijthe

Answer 2

有许多算法可用于解决魔方问题，然而，您可以参考这个最优算法http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

。请注意，此链接将带您进入维基百科页面。

- nicola

Answer 3

我不确定我理解你的问题以及你所说的快捷方式是什么意思。 如果你正在使用一些动态规划方法来解决魔方，你需要确保你向前看足够多的步骤才能达到解决方案。 我相信，如果你只支持2种移动类型（向右旋转，向上旋转），你需要向前看12步（不确定）才能在每次移动之前决定正确的移动，以确保解决方案。

如果你正在做类似这样的事情，并且发现你的内存空间已经用完了，那么请记住，你只需要保留你正在遍历的路径，以便决定正确的解决方案（而不是整个树）。

我成功地使用这种方法在Java中解决了魔方，所以C语言应该没有问题（就内存占用而言）。

- Asaf

Answer 4

魔方的状态空间大小约为2⁶⁵。盲目搜索状态空间的回溯算法可能需要检查大部分状态空间才能找到解决方案，因此显然简单的回溯算法不会很好地工作。但是，这个问题已经被解决了很多次。例如，请参见http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf。

- Antti Huima

Answer 5

如果您不关心移动次数，这里有一种方法可以将状态空间分割，以便您的暴力方法可以工作。

为菜鸟寻找魔方解决方案

• 首先，将所有魔方面（但不包括角落）暴力放置到正确位置
• 然后找到可以让这些面保持不变的移动方式（例如(f.g.f-1.g-1)^3）。实际上只需要两个移动。要找到它们，请考虑角落和非角落子立方体的排列，然后迭代角落循环长度的最小公倍数，以获得角落的不变量）
• 使用回溯算法将角落放置到正确位置（但它们仍然需要旋转以对齐颜色）
• 找到使魔方在同一段上旋转的神奇移动。 没有任何移动可以

- fulmicoton