做做AI，造造人 - 动力老男孩的博客

我们的快速魔方算法要隆重登场了，在此缺席感谢一下来自Netherlands的Jaap Scherphuis同学。看前面这个页面的第三名。

魔方表示法
咱们先看一串天书般的字母：UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
这种表示法是由一个叫Mike Reid的兄弟首先使用的，它表示一个已经被解好的魔方。
先不要被这串字母吓倒，看算法就像追mm一样，要迎难而上。仔细观察，你会发现其中只有六种字母：
U: Up
F: Front
R: Right
L: Left
D: Down
B: Back
其实这就是代表了空间坐标系的六个方向，就是传说中的“眼观六路”的那六路。
表示法中包含了12组双字母的组合，分别代表了魔方的12个棱，第一组UF就表示Up和Front之间夹角的棱。
另外还包含了8组三字母的组合，分别代表了魔方的8个角，每个角由三块颜色组成。看下面的示意图：

魔方坐标系

等等，细心的朋友至少会想到两个问题：
1，为什么没有中心的数据？
因为魔方的六个心在任何旋转过程中，相对位置都是不会变的，这点拆过魔方的人应该比较容易理解。
2，如果是一个打乱的魔方，棱和边的颜色已经和中心不一样了，这时候怎么表示？
读取方法是：按照刚才那个天书字符串的顺序，先找到UF位置所对应的棱，假设现在U是红色，F是黄色；
那么对照图里的中心，红色的中心是R，黄色的中心是U，所以这时候的第一组棱字母是 RU
嗯，希望你看到这里还没有晕车的感觉。

输出表示法
这个程序的输出是这个样子：F- U+ F- D- L- D- F- U- L2 D-
FRL之类的字母依然表示六个面，F-表示前层逆时针转90度，U+表示上层顺时针转90度，L2表示左边层转180度。
如果你是魔友的话，会经常看到这样的字符串：F’UF’D'L’F'U’L2D’
这是魔方论坛上比较常见的“黑话”，其实就是默认顺时针不加符号，逆时针的加一个单引号，180度的加2。
请注意这里的顺时针和逆时针使用的是“观察者迎着某个面看”的参照系，例如B’是从下往上看的逆时针，如果你没有把脑袋钻到桌子下，你事实上看到的是顺时针旋转。

改写到C#
这段程序是用C写的，说实话它的原理还比较复杂，有兴趣的同学可以搜索“Thistlethwaite’s algorithm”
我直接依葫芦画瓢用C#把它重写了一遍，请点击这里下载源代码。请主要要安装VS2008或更高版本。

http://www.diy-robots.com/RubikSolver/RubikSolverSample.zip

补充：如何使用这个程序

鉴于很多朋友询问如何运行这个程序，下载这段代码，用C语言的编译器编译成Jaap.exe。然后在命令行输入：
Jaap.exe UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

输出结果就是类似 F- U+ F- D- L- D- F- U- L2 D- 这样的步骤。
注意这段程序没有验证功能，如果你输入的颜色表达式错误，会导致程序死循环或者错误。以我的经验看，普通电脑都能在1秒以内算完，如果你一秒钟还没有看到结果，就检查检查输入吧。

本来我想把这个攻略做成一个NXT开发的教程，把传感器，电机，发声等部分都介绍一遍。不过现在看来有些同学很心急，希望早点看到“核心代码”，所以我提前把解魔方的算法写出来。其实魔方的算法网上有很多，只要你耐心并且有效的使用搜索引擎，会发现上个世纪就已经有人公布算法或源代码了，例如
算法：http://www.zunny.com/RUBIK.HTM
代码：http://tomas.rokicki.com/cubecontest/

不过我做第一版的时候，还是决定自己动手写算法。原因很简单：我玩魔方很多年了，把玩法转成算法也是我的目标之一。在写程序之前，我画了以下的几张草图：

魔方算法的草稿

 话说曾经有位同事本打算和我一起做萝卜头的，看了这些草图以后，决定还是继续打游戏更靠谱。这不禁让我想起一首歌“1979年，那是一个春天，有一位老人在中国的南海边画了一个圈…” 这位老同志一定是资深软件架构师，改革开放这么宏伟的事情，画个圈就搞定了。
这样说来我这个草图是太复杂了，难怪把人吓跑了。今天特地又重画了些好看的图，以便大家理解。

魔方表示法
算法的第一个问题就是，怎么用数学方式描述一个魔方状态。我的做法是把魔方想象成一个纸盒子，沿边缝剪开铺平，就形成了六个面，我按照图里的顺序给它们编了号。
每个面又包含了9个颜色小方块，我也按照图中的顺序给它们编了号。

魔方的数组表示法

这样一来，立体的魔方就变成了一个 6*9 的数组。例如下面是一个普通的被打乱的魔方：

static String SideColors[] = {
  "orgorwwoo",
  "oyggbobrg",
  "yyrgowwbw",
  "yrybgybbo",
  "gwwyybror",
  "bgrwwrbgy"

魔方坐标系：
啥？怎么又有坐标系，刚才的表示法不就完全描述了一个魔方吗？没错，但是咱们的萝卜头每次只能旋转魔方的最下面一层，假设我们需要旋转最上面一层，就必须先把它翻到下面。
请注意在翻跟头的过程中，魔方本身并没有变化，只是坐标系变了。所以还需要一个坐标系来对应萝卜头的空间：

魔方坐标系

状态变化：
正如刚才所说，魔方在萝卜头的数字世界里有两种变化形式：1，翻跟头；2，旋转某一面。
每次状态变化都会造成SideColors数组发生变化，这种转换用最简单的查表法就可以搞定：

坐标变化的大概示意图，坐标变化没啥难度，主要看耐心

例如，这是一段旋转底面后状态转换的代码：

public static void RotateBottomSide(boolean ClockWise) throws Exception
{
 int temp=0;
 int i;

 CopyMatrics(2,6,ClockWise?2:1); //Bottom ClockWise = Top Anti-ClockWise
 CopyMatrics(6,2,0);
 if(ClockWise)
 {
  for(i=0;i<3;i++)
  {
   temp=Sides[5][0][i];
   Sides[5][0][i]=Sides[3][2-i][0];
   Sides[3][2-i][0]=Sides[4][2][2-i];
   Sides[4][2][2-i]=Sides[1][i][2];
   Sides[1][i][2]=temp;
  }
 }
 else
 {
  for(i=0;i<3;i++)
  {
   temp=Sides[5][0][i];
   Sides[5][0][i]=Sides[1][i][2];
   Sides[1][i][2]=Sides[4][2][2-i];
   Sides[4][2][2-i]=Sides[3][2-i][0];
   Sides[3][2-i][0]=temp;
  }
 }
}

CFOP解法：
这是由一位叫Jessica Fridrich女士发明的一种速解法，是目前世界上最流行的方块解法。
CROSS：字面上的意思为“十字”，是Fridrich Method中的第一步骤。
F2L：是“First 2 Layer”的缩写，意思为“一、二层”，是Fridrich Method中的第二步骤。
OLL：是“Orientation of Last Layer”的缩写，意思为“最后一层的角块排序”，这是Fridrich Method中的第三个步骤。
PLL：是“Permutation of Last Layer”的缩写，意思为“最后一层的排序”，这是Fridrich Method中的第四步骤。
CFOP：是Fridrich Method的的别称，就是四个步骤“Cross、F2L、OLL、PLL”原文的第一个字母合起来而成的。

上面这些文字比较费解，看下面的图就比较清楚了：

魔方的CFOP入门解法

或者你可以去魔方小站或者魔方吧看更详细的教程。

CFOP解法的实现：
这一部分比较繁琐，输入玩法公式的输入，按照上面的步骤实现以下函数：

TopCross();
TopCorner();
SecondLayer();
BottomCross();
BottomCorner();
ThirdLayerCorner();
ThirdLayerCornerSnap();
ThirdLayerBorderSnap();

CFOP算法的源代码可以点这里下载
通过这个CFOP算法，萝卜头完成了第一版：http://v.youku.com/v_show/id_XNDcwMDQ3NDQ=.html

这个算法的最大问题就是步骤太多，一般来说要120步左右，平均时间12分钟，大多数观众等不到转完就睡着了……
因为这个原因，我改用了一个更快的算法。写博客真是挺累啊，这个算法下次再介绍，心急的同学请看下面这个链接：
http://tomas.rokicki.com/cubecontest/ 点最上面的Winners，我用的是第二名的算法。