较短步数复原魔方的算法

这其实是我们上学期程序设计课的一个大作业，我很早就想把它记录下来了，可是实在太懒了就拖到了这个学期。本来作业是要求复原魔方就好了，但是后来发现没有图形界面的话似乎调试很困难，就顺便写了一个 UI，刚好还学了一下 OpenGL。最开始我是写了能够找到最优解的 Krof 算法，但是估计是我写得比较丑再加上状态空间实在太大了（大约在搜索到第 15 步还是 16 步的时候状态数就到百亿级别了，而我 8 个线程一秒只能搜几千万个状态好像），根本没有办法在可以接受的时间内得到解。于是退而求其次，改为去搜索一个比较优的解，最后基本上一秒以内就可以得到解了。

整个工程的代码我放在了我的 Github 上。

魔方的表示

如何表示一个魔方呢？一个很直接的方法就是用六个面一共 54 个色块来表示它，我在最开始写的时候就是用这种方法来表示一个魔方的，但是这样存在着很多的冗余。事实上，我们可以按照魔方的各个棱块和角块的位置和方向来存储。对于魔方的一个角块来说，我们只需要存储这个块在 8 个角的哪一个地方以及它的方向如何（关于方向接下来会进行规定）。对于棱块来说也是相同的，只需要位置和方向就可以决定了。

角块方向的表示

首先对于一个角块来说它可能会有 3 个不同的方向（如下图，暂不考虑这个魔方是否合法，仅关注角块）

想象一下，从左到右相当于单独把面对我们的这个角块（按照从魔方中心指向该角块顶点的向量）旋转了两次。我们可以按照这样来规定角块的方向：首先将对应角块像上图中一样面对我们，并且以绿色或蓝色作为顶面。现在以绿色或蓝色作为参照色（因为一个角块有且仅有这两种颜色之一）。现在来规定角块的方向：

• 如果参照色位置在如同第一张图一样的位置，就规定方向为 0
• 如果参照色位置在如同第二张图一样的位置，就规定方向为 1
• 否则就规定方向为 2

棱块方向的表示

对于棱块方向的规定就稍微有些复杂了，因为没有办法像角块这样找到对立的两个面使得每个棱都包含这两种颜色之一。那么对于棱块的参照色我们规定：如果一个棱存在蓝色或绿色，则该颜色为参照色，否则白色或者黄色为参照色。规定了参照色之后就可以规定棱块的方向了：

• 如果棱块位于顶层或者底层（也就是绿色或者蓝色面所在的层），那么当参照色在这两个面中的一个时方向为 0，否则为 1
• 如果棱块位于中间层，那么当参照色在白色或者黄色面时方向为 0，否则为 1

在第一张图中，两个棱块的方向都是 0。这是因为对于红白色棱块，白色为参照色并且其位于顶层绿色面；对于绿白色棱块，绿色为参照色并且位于中层白色面。

在第二张图中，两个棱块的方向都是 1。原因与之前的刚好相反。

Kociemba 算法

首先我们规定一种魔方的中间状态：仅仅通过 U、D、L2、R2、F2、B2 这几种旋转就可以将魔方复原的状态。也就是不允许 $90^\circ$ 地旋转魔方的前后左右这四个面。这种状态有什么特点呢？

首先很明显可以观察到按照我们刚刚规定的方向，旋转顶面和底面都是不会改变棱块和角块的方向的，并且仅按照 $180^\circ$ 来旋转周围四个面也是不会改变棱块和角块的方向。那也就是说，在这种中间状态下，魔方的棱块和角块的方向应该都是 0，这是因为目标状态的魔方如此。除此之外，魔方中间层的四个棱块必然也在中间层。

可以简单地计算出这种中间状态一共只有 $8! \times 8! \times 4!=3.9 \times 10^{10}$ 种可能，事实证明，在不超过 $18$ 步以内就可以从这种状态复原魔方。我们用 IDA* 来进行搜索，当我们设计启发函数的时候分别针对角块（一共 $8!$ 种可能）、顶层和底层的棱块（一共 $8!$ 种可能）、中间层的棱块（一共 $4!$ 种可能）计算复原它们所需要的最少步数（这可以直接进行搜索），之后的启发函数就是这三者的最大值。

剩下的问题就是如何将魔方旋转到中间状态，我们同样采用 IDA* 来进行搜索。对于启发函数，分别针对角块的方向（一共 $38$ 种可能）、棱块的方向（一共 $28$ 种可能）、中间层棱块的位置及方向（一共 $A^4_{12} \times 2^4$ 种可能）计算复原它们所需要的最少步数。经过计算，不超过 $12$ 步就可以将一个魔方旋转到中间状态。这样总共在不超过 $30$ 步的情况下就可以复原一个魔方了！

刚刚的状态表示方式在这个算法里显示出了很大的优势，在进行 Hash 的时候可以直接使用这个状态表示，而不必从其它表示方法（例如存储 $54$ 个面的方法）计算出棱和角的方向。事实证明，在通常情况下，这个算法很快就能够复原一个魔方。

Krof 算法

这个算法就是我前面说的搜索最优解的算法，思路和 Kociemba 算法几乎一样，不过 Krof 算法没有划分阶段，启发函数是分别对于角块的方向和位置（一共 $8!\times 37$ 种可能）、两组每组 $6$ 个梭块的位置和方向（每组都是 $A^6_{12}\times 2^6$ 种可能）计算复原它们所需要的最少步数。由于这个启发函数的计算也是十分耗时的，所以可以先计算一次之后记录下来之后直接读取就可以了，而前面 Kociemba 算法的启发函数可以现场计算。