algorithm - 求解 NxNxN 魔方的算法

Question

我想为任何大小的魔方写 cubesolver 。

我知道如何解决大于 3x3x3 的立方体：

• 首先我们需要求解立方体的中心（平面）场，所以它们看起来像图片上的那样。

• 其次，我们解决边缘：

• 最后，我们可以将整个问题简化为解决 3x3x3 立方体：

---

这听起来很简单，但问题是解决中心和边缘的方法取决于立方体的大小。对于求解中心和边缘的 3x3x3 算法有 0 个移动，对于 4x4x4 它更长，对于 5x5x5 它甚至更长。

但是我如何计算这些移动呢？有什么简单的方法吗？

提前致谢！

Answer 1

通过将每种移动视为一种排列，您可以将其视为群论中的一个练习。然后，您需要确定立方体的加扰顺序是否等于某些可用排列的某个顺序的乘积，如果是，那么该顺序是什么。

事实证明，有一些算法可以解决这个问题，还有一些非常复杂的计算机包可以实现它们。对于包和主题，一个起点是http://en.wikipedia.org/wiki/Computational_group_theory。

Knuth 在http://arxiv.org/pdf/math.GR/9201304.pdf上引用了一种可实现的算法。我已经实现了这个版本，所以它是可行的，但是论文非常密集 - 请参阅我在关于解决滑动瓷砖拼图的方法中对它的引用。如果您比我了解更多的群论，您将能够阅读更密集的论文并实现更有效的算法。哦——如果你读完这篇论文，你首先应该能够找到问题是否可以解决，然后，理论上，找到一个可以解决它的排列序列，但这个序列可能不切实际地长。

此特定算法与您上面概述的方案并没有完全不同，因为它寻找可用移动的组合，以保持某些对象被置换固定，同时将另一个对象恢复到适当的位置。