由 动力老男孩 发表于 2010/01/05 22:16:38
我们的快速魔方算法要隆重登场了，在此缺席感谢一下来自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秒以内算完，如果你一秒钟还没有看到结果，就检查检查输入吧。