Cppowboy

     最近刚学习完C++的一些基本知识，之后要完成一个魔方求解的命令行小程序。起初没有什么思路，捉不到头绪。后来查阅了各种资料，并向好友寻求了帮助，终于找到了解决的办法。今天在这里记录一下解决的思路和方法，与大家分享。个人水平有限，难免有错误和不妥善的地方，欢迎大家批评指正。

     魔方求解的常见方法，大致有三种：逐层法，CFOP法以及搜索法。逐层法是比较常见的方法，大部分在学习解魔方的过程中都是采用这种方法，但是这种方法比较繁琐。有的同学在写的时候用了大量的if-else，不仅代码复杂，而且不便于维护。CFOP是解魔方的高级方法，与一般解魔方的方法不同，CFOP算法采用了非常明确的几个步骤，但是公式较多，对人来说比较难于记忆，但是编程实现难度不一定就比逐层法困难。搜索法要用到群论的一些思想，数学要求较高，但个人水平有限，并没有弄懂这种方法的具体思路。

      基于以上原因，我最终选择了CFOP算法解决问题。CFOP算法分为cross, first two layers, orientation of last layer, permutation of last layer四个步骤。各部分有不同的公式，有的一步二十多个公式，有的却要五十几个公式，如果也用if-else来进行各种判断的话，实在是有点繁琐，这里我采用了一种match的方法，将魔方与对应的情形进行比较，如果匹配成功，就执行相应的公式，直到解决问题。具体地，在进行比对时，将整个魔方转换成一个字符串，只存储各位置的颜色与各面颜色的相对关系（某个面的颜色指的是此面中心处的颜色），如果一个位置颜色与顶面中心颜色相同，则记为U，类似地有D（底面）,L（左面）,R（右面）,F（前面）,B（后面）。并且存储时按块存储，即UF UR UB UL FL FR BL BR DF DR DB DL UFL UFR UBR UBL DFL DFR DBR DBL,其中UF指的是顶面与前面相交的棱块，UFL指的是顶面，前面，左面相交的角块。容易发现，UF UR UB UL FL FR BL BR DF DR DB DL UFL UFR UBR UBL DFL DFR DBR DBL表示的是一个恢复原关的魔方，如果一个魔方没有恢复原状，则UF处就写为顶面与前面相交的棱块的顶面相对颜色和前面相对颜色。其它的位置类似。解决了表示的问题，剩下的就是匹配当前魔方的状态与公式所表示的状态。每个公式所表示的状态表示为一个字符串，关键位置就具体的相对颜色表示，无关部分用空格表示，这样只需逐个比较当前魔方的字符串与公式所对应的字符串的相同个数，就可以判断当前是否可以使用此公式。

代码地址：http://download.csdn.net/detail/u010526186/6812555

个人水平有限，如果其中有什么错误和疏漏欢迎大家批评指正。

panyx93@163.com