解决NxNxN魔方的算法

Question

我希望编写任意大小的魔方求解器。

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

第一步，我们需要解决立方体中心（平坦）区域，使其看起来像图片中那样。

其次，我们解决边缘：

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

听起来很容易，但问题是解决中心和边缘的方法取决于魔方大小。对于3x3x3，解决中心和边缘的算法不需要操作，对于4x4x4，它更长，对于5x5x5，它更长了。

但是我该如何计算这些操作？有没有简单的方法？

提前感谢！

- Firzen

---

这是一个非常有趣的问题，但我怀疑这个问题没有简单的答案（或者任何适合在SO答案中的答案）。你最好在谷歌上搜索一些特定的算法。 - templatetypedef

为什么你会对有赞和收藏的问题置之不理？你真的认为我没有尝试过搜索算法吗？如果Stack Overflow能做的只是搁置我的问题，那么...真的谢谢了。 - Firzen

晚来的评论。对于4x4x4，配对边缘会干扰中心块。在配对中心之前配对边缘会更简单，这样配对边缘就不需要恢复被干扰的中心块。相比3x3x3，4x4x4引入了新的奇偶性，可以交换2个边缘对，可以翻转1个边缘对，中心块可以移动。5x5x5或更大的魔方不会引入任何新的奇偶性问题。类似于3x3x3或4x4x4的序列可以用于NxNxN魔方。 - rcgldr

Answer 1

你可以把这看作是群论练习，通过将每种移动视为置换来考虑。然后，您需要找出魔方的混乱顺序是否相当于一些可用置换的某些顺序的乘积，并确定该顺序。

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

一种可实现算法的参考文献是Knuth在http://arxiv.org/pdf/math.GR/9201304.pdf中提到的。我已经实现了其中的一个版本，所以它是可行的，但是这篇论文非常密集 - 参见我对其的引用Regarding approach to solving sliding tiles puzzle。如果你比我更了解群论，你将能够阅读更加密集的论文并实现更高效的算法。哦 - 如果你通过这篇论文，你应该首先能够找出问题是否有解，然后理论上找到解决它的排列序列，但这个序列可能不切实际。

这种特定的算法与您上面概述的方案并没有完全不同，因为它寻找可用移动的组合，使得一些被置换的对象保持不变，同时将另一个对象恢复到其正确的位置。

- mcdowella