首先上我自己实现的github链接：kociemba 输入方式可以看readme，这是一个成熟可用的小项目，虽然没有进行多核优化，只能跑一个cpu，但在一般的x86机子上，即使是设定20步的解法， 大部分的case也都能在1s之内给出解法。 我做了扫描输入的方法，扫描的顺序如下

这个输入方法可以接入opencv，当然本套算法没有接入，如果要测试，可以手写

--------------------------------------------------------------------------------------------------------------------分界线，以下为算法详解

三阶魔方不是最简单的魔方，但是大多数人第一次接触的魔方就是三阶魔方 计算机解魔方 与人类使用的层先 ，CFOP等方法有所不同，简单来说就是两个字：搜索 我们知道 ，三阶魔方不算复杂，但是它的不同可能的形态也是一个庞大的数字 棱块方向 * 角块方向 * 棱块排列 * 角块排列 / 去除一半的非法角棱组合 2^11 * 3 ^7 * 12! * 8! / 2 = 4.325 * 10^19 如果穷举来搜索，对任何个人计算机来说都是不可能完成的任务,因此 如何降低搜索复杂度是关键问题。

开始了解具体的算法之前，需要对魔方进行编码，三阶魔方有20个可移动的块，包括8个角块，12个棱块，魔方的六个面 分别定为U（up）、 D（down）、 F（front）、 B（back）、L（left）、R（right） 当我们描述某个面旋转的方向时，一定是当你正对此面时的旋转方向，编码需要考虑两个方面，一是每个块的方向，另一个就是每个块的位置。 首先进行初始编码，将一个还原好的魔方中心块固定，按照自己方式分别对12个棱块和8个角块进行编号。这样，每一个块本身的编号是什么就固定下来了，另外，将还原好的魔方的每个块的方向定为0， 根据自己的方法将棱块的其余一种状态进行标记（例如1），角块的其余两种状态进行标记（例如1,2）

对一个打乱的魔方进行编码，就是按照之前初始编码的顺序，依次查询每个对应的位置上分布的是哪个块，有可能是正确的，也有可能是其他位置上的块，将每一个块的编号和方向按照初始编码顺序记录下就得到了一个编码好的魔方，这里有一个难点是当某个位置的块并不正确时，该块 方向的判定，可以按照以下规则： 对角块，以U/D面为基准，当某个块U/D面的色在U/D面时候，其状态即为正确，否则观察其U/D色那一面逆时针旋转了几次，旋转一次标记为1，旋转两次标记为2 对棱块，由于不是每个棱块都有U/D色，不能以U/D为基准，这里定义魔方的六个面为三组，U/D为高级色，F/B为中级色，L/R为低级色 ，对于某个棱块，若其更高级的色在其所在位置更高级的面，则视为颜色正确，标记为0，否则错误，标记为1，例如：FR这个棱块在UR棱块位置，若其F色在U面，则其状态正确，标记为0，若R色在U面，则其状态错误，标记为1. 根据以上规则，可以将一个打乱的魔方进行编码，扫描式的魔方状态输入，就需要使用这个方法

了解kociemba算法之前，首先需要了解另一种魔方发明早期的魔方解法：Thistlethwaite 法 此方法法将一个魔方由打乱到完全还原分成了，四个阶段 第一阶段 还原十二个棱块方向 第二阶段 还原八个角块方向，同时要保证中层的四个棱块都在中层位置 第三阶段 调整角块相对位置，并且所有两个对面的色都要在这两个对面上（即F/B面的颜色必须全部在F/B面， U/D面的颜色必须全部在U/D面，L/R面的颜色必须全部在L/R面） 第四阶段 完全还原魔方 此方法是由 Thistlethwaite 这位数学家发明的，由此命名，此法又名降群法，有关群论等原理请自行了解。 四个阶段，每一个阶段完成后剩余总组合数量都会大大减少，并且每个阶段到下一个阶段都不算特别复杂。 经过一些更细的步骤划分后，此方法是一种人类可以使用的还原魔方的方法（看此处 不建议新手尝试）

而本文的主角 kociemba 就是将 Thistlethwaite 法前两个阶段合并，后两个阶段合并，因此 kociemba又被称为二阶段算法 到现在为止，kociemba的基本思路就已经出来

第一步，完成所有块的方向，并且保证中层的棱块全部都在中层 分解为三部分来考虑 1.角块方向 2.棱块方向 3.中层棱块位置 第二步 直接完成整个魔方，同样也分解为三部分来考虑 1.角块位置 2.非中层棱块位置 3.中层棱块位置

计算机解魔方自然是搜索，如何搜索 ，如何剪枝就是重点 我们使用IDA* 算法 ，自然就要考虑启发函数如何设计 ，使用什么条件来剪枝 启发函数通常来说是一个距离目标状态的距离， 我这里我们的条件是，距离目标状态的步数， 你可能会问，你怎么能知道和目标状态的步数？

答案是：直接穷举，将之记录

前面已经说过，魔方有4.3 * 10 ^ 19种case，这个数目很恐怖，但是，经过分解之后，却是可数的 例如角块方向，每个角块有三种情况， 那单考虑角块方向有 3 ^ 7 = 2187种情况，(为什么不是 3 ^ 8 ？ 这是魔方的性质决定的，想象一下，把魔方的一个角块揪一下，你怎么转也是还原不了的，这个可以自己验证)

我们将一个还原好的魔方使用BFS进行搜索，每次搜索只关注一种属性(包括角块方向，角块位置，中层棱块位置，棱块方向，棱块位置)，搜索的深度就是其距离目标状态的步数，如果经过某次移动后的状态已经被记录就略过，这样，搜索的次数其实是很少的，很快就能搜索完毕，将搜索出来的结果存入数组，后续搜索就可以直接使用。

以一阶段为例，第一阶段的目标是对好所有块的方向和中层棱块的位置，我们分为三个部分，棱块方向，角块方向，中层棱块的位置，这三种属性的总状态数分别是2048,2187,24( C(4,12) ),可以看到，单个属性的总状态数是非常少的。

需要注意的是,我们使用数组来存每种属性所有可能状态距离目标状态步数的值，为了后续使用时能够正确索引我们需要规定一种算法，来使每种状态都有其独一无二的值，这些属性有不同的编号方法，需要用到排列组合有关的知识，这里不赘述，把这个值记为IDX,在搜索过程中，除了记录某种状态距离目标状态的步数，还需要另一个二维数组，它记录每一种状态进行某次转动后的那种状态的IDX，这样，在后续进行实际的解法搜索的时候，就不再需要真正的进行方块转动，只需要在这个数组里面来查值，这能极大的提升搜索的效率。

由于以上的搜索需要耗费一些时间，可以将其存文件 前面的内容，都是进行解法搜索之前所做的准备工作，接下来，是搜索的过程

搜索的启发条件是距离目标状态的步数，每个阶段需要考虑三种分解条件（我的算法将三种合并为了两种），将当前状态距离目标步数的值记为三种分解情况的最大值，当这个值为0时，就达到了目标状态。在这个过程中，有两个剪枝条件： 首先是第一个，由于我们使用IDA* ,是限制了搜索深度的，如果我们发现当前状态进行了某种转动之后的状态距离目标的步数已经大于当前深度的余量，那么，在当前限制深度的条件下，进行此种转动是不能得到满足步数的解法的， 就可以将其剪掉，不再继续向下搜索，这是最主要的剪枝手段 第二个，如果上一次转动的面与当前要转动的是同一个面，那就不再进行，直接跳过，这个剪枝条件不过多赘述，很多关于搜索的算法中都有类似的剪枝手段

经过大量的实际情况统计发现，阶段一的解法一般在9-10步就会开始出现，但是大部分情况下，阶段二的解法都在13步以上，为了找到足够短的总步数解法，可以限制阶段二解法深度在10步或者11步，如果没有找到这么短的解法，就不采用当前的阶段一解法，继续搜索，直到找到足够短的阶段二解法。