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

解魔方的机器人攻略18 – 魔方快速算法

由 动力老男孩 发表于 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秒以内算完，如果你一秒钟还没有看到结果，就检查检查输入吧。

快速解法 算法 魔方

对 “解魔方的机器人攻略18 – 魔方快速算法” 的 61 条 评论

1. dead_lee 说：

   2010/01/05 于 22:59

   不錯不錯, 慢慢看.

   回复
2. ZAE 说：

   2010/01/06 于 04:17

   继续关注
   CB观光团

   回复
3. dot 说：

   2010/01/06 于 14:09

   持续关注

   回复
4. Magnus 说：

   2010/01/07 于 12:28

   lz,我记得你是不是用java开发的? 转战.net了? 请问微软那个开发平台怎么样?

   回复
5. Sirit 说：

   2010/01/09 于 17:06

   都看完了，好想买一个来做个玩魔方的机器人。

   回复
6. 路过 说：

   2010/01/11 于 09:43

   路过，看看

   回复
7. 路人 说：

   2010/01/13 于 19:16

   我觉的“人工智能”相当的虚幻……加油～呵呵。关注。

   回复
8. 过后 说：

   2010/03/09 于 15:58

   膜拜，代码拿走了，研究一下

   回复
9. lechie 说：

   2010/03/26 于 13:01

   我发现了一个错误，我觉得那句“会发现其中只有六种字母”两个B是不对的，其中一个B应该是D吧，DROP？底下，另一个就是B，Back

   回复
   • 动力老男孩 说：

     2010/03/26 于 13:42

     果然是我搞错了，多谢纠正！
     正确的是D，应该是Down的意思，也是“下层”
     

     回复
10. 会飞的鱼 说：

    2010/07/23 于 21:01

    LZ能不能详细一点的介绍下还原模仿算法是怎么设计的？怎么扫描一次算法就出来了呢？我现在也在研究拧魔方…算法完全没头绪…

    回复
11. 求魔方搞笑算法 说：

    2010/07/31 于 01:23

    楼主，请问你这个程序解出来的一般要多少步？有没有50步以内的？机器人时间限制……

    回复
    • 动力老男孩 说：

      2010/07/31 于 17:06

      这个算法一般在三十步以内

      回复
      • qigai 说：

        2010/09/16 于 19:16

        Stefan Pochmann的程序怎么在我的vc上编译通过但运行有问题

        回复
        • 动力老男孩 说：

          2010/09/16 于 23:15

          唉，我后来查了，其实应该感谢的是第三名Jaap Scherphuis
          请下载第三个编译吧

          回复
          • qigai 说：

            2010/09/17 于 09:15

            谢谢回答！
            不过我下载了所有的程序只有第十名Yuri Pertsovski的有用而且有魔方测试过后也正确就是有时步骤有96步之多
            其他的程序都出现
            诸如”0×00402569″指令引用的”0×00000000″内存。该内存不能为”read”。
            的错误
            有什么办法解决吗？
            有什么办法吗很期待有３５步之内的算法，
          • 动力老男孩 说：

            2010/09/17 于 10:46

            这位同学，我建议你再尝试一下第三名Jaap的程序
            我当年也是从第一名的开始试，到Jaap的这个才发现可用
            出错的话你查查32位或64位系统的原因，或者输入数据是否正确
            这个算法一定能在35步之内搞定的
12. qigai 说：

    2010/09/21 于 08:46

    原来他们用的是带参数的main函数，程序只能在命令行下敲命令，他们的程序好像除了第一个有编译问题外，其他的都能用。
    自己真是个菜鸟，麻烦高人了，以后一定多看书。

    回复
    • darkorigin 说：

      2012/05/05 于 13:11

      你也可以自己做个外壳程序，用调用这个程序的方式来，然后读出调用的参数显示出来（还可以翻译成常见的语言 比如 第一步旋转90度某层，第二步。第三部。。。。。等等）

      回复
13. 不懂魔方算法 说：

    2011/03/02 于 20:15

    楼主，我刚学C语言没多久，看不懂你说的Jaap的程序。
    想问问楼主，Jaap的程序中，哪个变量是输入魔方的初始状态的？哪个变量是输出魔方解后的步骤？请指点!

    回复
    • 动力老男孩 说：

      2011/03/02 于 22:40

      args了解吗？
      ***.exe UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

      回复
      • 不懂魔方算法 说：

        2011/03/05 于 12:17

        哦，我运行完后，它输出 D1F3U2L3B1R1B2D3L3U1F2R1D1L2D1R2D3R2D1L2B2D1
        我们玩魔方通常是以F表示顺时针转，F’表示逆时针转，F2表示180度转，
        但是它输出的F1,F2,F3是怎么转啊？

        回复
14. 怎么用啊 说：

    2011/04/29 于 20:24

    怎么用啊，就一个输入输出，输入是输入啥啊？颜色吗？怎么输入啊？

    回复
    • 动力老男孩 说：

      2011/04/29 于 22:28

      加了一段补充，在文章最下面。

      回复
15. cloud 说：

    2011/07/03 于 11:51

    我发现这个版本的Jaap的程序(http://tomas.rokicki.com/cubecontest/jaap.zip)并不完美。有时候当输入是正确的时候，比如DB RF LD RD LU UR DF RB LB LF FU UB FRU URB DRF ULF BLU LBD RDB FLD (又比如是UL UR DF BL LF RD UB UF DB RF DL RB LDF RFD LBD RUF BRD URB ULF LUB)，Jaap的程序会进入很长的循环(不知道是不是死循环)，体现在你的winform程序上就是界面没反应。请注意这个输入是经过验证的正确的输入。

    回复
    • 动力老男孩 说：

      2011/07/03 于 21:46

      嗯，我也发现这个问题了，记得还有一个明显的问题，是转动90度的情况，有时候它会转180，然后回转90。不过现在有更好的方案了，你搜一下cube500

      回复
      • cloud 说：

        2011/07/04 于 00:35

        百度和google都没找到关于cube500的有用消息。不知道你指的是什么，能不能给我一个连接？

        回复
        • 动力老男孩 说：

          2011/07/04 于 12:01

          抱歉抱歉，cube500是我当时下载的zip文件名，这个全称叫cube explorer 5.00
          http://kociemba.org/cube.htm

          回复
          • cloud 说：

            2011/07/05 于 13:50

            看到了。我下载了它的GUI_example.jar，写的非常清楚。我和你一样，也需要把它变成c#。于是我就花了一点时间把里面的java code改写成c#，不料随便计算一个random的cube就用1分钟的时间。我检查了半天，并没有发现修改过程中引入的错误，而且最终的输出结果也是正确的。用了vs profiler和ants profiler，发现不知为什么，整体的时间就是比java的要慢，其中一个 if ((index & 1) == 1)的语句更是瓶颈，居然总共占用了40%的时间。可是奇怪的是我在c#和java下做的测试显示就此语句c#并不比java慢。然后我又用了ikvm试了一下，发现ikvm转换出来的dll有同样的问题，一样很慢。上来牢骚一下，不知道你有没有什么建议。
          • 动力老男孩 说：

            2011/07/05 于 22:27

            我没研究过那个算法，不过它需要先生成一个离线的数据库，感觉应该是索引文件吧
            你创建了吗？
            我直接用它的工具，每次都是1秒以内，偷懒的话可以用它的URL接口，在C#中用httpRequest请求
          • cloud 说：

            2011/07/06 于 02:56

            对的，它开始的步骤是创建一些pruning table，99%的时间就是耗在了这个上面。我后来想了个办法，就是把生成的pruning table和其他的一些索引文件都序列化到二进制文件里，因为这些数据是不变的。真正的程序开始运行的时候就从这个文件里反序列化，而不需要每次都计算一次。这下每次求解就只要大概几十或几百个毫秒了。

            谢谢你的热心帮助！
          • 动力老男孩 说：

            2011/07/06 于 22:10

            恭喜cloud同学
        • darkorigin 说：

          2012/05/05 于 13:20

          可以把你做好的程序贴出来么？
          建议共享呵呵~~~学习下~~~~

          回复
          • ntwuhui 说：

            2012/06/26 于 00:41

            经调试，排名第一的程序也可以使用，程序中采用了大量宏定义，真是服了！！
          • 动力老男孩 说：

            2012/06/26 于 22:08

            那个程序可读性特别差，我怀疑是手工写好代码之后，然后用压缩工具混淆的
          • WFQ 说：

            2013/02/26 于 22:23

            排名第一的程序不能编译啊，其它不错！
            Cube Explorer 5.00的解最优。
16. Neil 说：

    2013/01/31 于 02:31

    我把你c#里的算法直接加到nxt的程序里，我靠，这nxt别提算的有多慢了

    回复
    • 动力老男孩 说：

      2013/02/02 于 20:35

      对，nxt算这个东西太吃力了

      回复
17. qinghao 说：

    2013/07/25 于 10:07

    干啊，我前两天才想到这个，结果哥您都玩了好久了。

    不过没得事，我也是看了你哥的四轴相关文章才被点燃要做四轴的。

    回复
18. 0x5e 说：

    2013/08/15 于 01:27

    我下了cube500网站里提供的twophase.jar,按照GUI_example.jar里的用法,想把它移到android上去,现在可以生成随机魔方,但是解不了,运行到解魔方那里就会卡住几分钟都没反应.. 不知是手机处理能力太弱了还是什么??你知道为什么吗

    回复
    • 动力老男孩 说：

      2013/08/17 于 09:52

      要预先生成一个几百兆的哈希查询表，我没有处理过，是听之前的一个朋友说的

      回复
      • 江南 说：

        2017/06/01 于 09:06

        楼主你好，我看评论说目前的cube500 这个算子目前最快，20步之内，搜索了好长时间，只有软件，没找到源码，楼主可以给个源码链接吗？

        回复
19. 马吃鱼 说：

    2013/12/19 于 11:29

    你好老男孩，现在我在根据你的教程在做机器人，但是我手边的电脑没有蓝牙设备，因此想要请教如果想通过usb通讯的话pc端c#应该怎么写啊？
    我觉得应该就是这个部分，能否帮我看看应该如何改写？谢谢！
    public Form1()
    {
    InitializeComponent();

    //Get all port list for selection
    PortList.Items.Clear();
    string[] Ports = SerialPort.GetPortNames();

    for (int i = 0; i 1) PortList.SelectedIndex = 1;

    DisplayWindow.Navigate(new Uri(Application.StartupPath.Replace(@”\bin\Debug”, “”) + @”\rubik.htm”));
    }

    回复
    • 动力老男孩 说：

      2013/12/23 于 21:45

      你用USB连接乐高吗？这个我也不太会，不过买一个USB的蓝牙适配器很便宜的，应该是二三十块钱

      回复
20. 陈兴达 说：

    2014/02/17 于 10:56

    动力哥，加我qq447172764，代码有些地方没理解，好纠结，看了好多天了
    …

    回复
    • 动力老男孩 说：

      2014/02/18 于 09:46

      不好意思啊，工作忙，加QQ太影响工作。有问题可以发邮件给我，邮件地址看右侧栏最下面。

      PS：现在魔方算法已经有很多改进了，比我这个好用，你可以搜一下 cube explorer

      回复
21. 潘伟豪 说：

    2015/09/02 于 17:11

    http://51036fc1.nat123.net/webMF/cube/CubeAction_test.action
    花了一年的时间改造的程序，还原平均步数大约是100步，运行时间大概4~5秒，原理和以前一样，Dijkstra算法+空穴法。博主有兴趣的话可以Q我一下：1252985278，我打开服务器上面的网址就能访问了

    回复
    • 潘伟豪 说：

      2015/09/02 于 17:21

      补充一下，魔方的基础操作是12种时，还原平均步数大约是100步；
      基础操作是18种时，还原平均步数大约是80步；

      回复
      • 动力老男孩 说：

        2015/09/04 于 10:25

        自己写的算法，能到这个程度相当给力了！
        赞！

        回复
22. LY 说：

    2015/09/28 于 20:39

    博主你好！请问是这第三名的算法快，还是17结尾说的第二名的快？？另外 能否给第二名的代码一个大致的讲解？

    回复
    • 动力老男孩 说：

      2015/09/29 于 09:25

      现在最快的是 cube explorer，1秒内计算完毕，解法不超过20步

      回复
23. 黄锐 说：

    2015/10/11 于 11:52

    j=strchr(faces,argv[i+1][f])-faces;这里总是出错是怎么回事

    回复
    • 动力老男孩 说：

      2015/10/12 于 10:59

      你的输入参数不对吧，argv是命令行后面带的参数

      回复
24. 孤影 说：

    2015/10/28 于 02:41

    动力老男孩你好,我最近也在做个魔方机器人的项目.
    GUI_example.jar你用c#重写过了吗?能否发个代码?

    回复
    • 动力老男孩 说：

      2015/10/31 于 19:42

      没有啊

      回复
25. 参考动力老男孩的解析进一步了解程序 – 掰搿实验室 说：

    2016/08/22 于 11:30

    [...] 动力老男孩 [...]

    回复
26. 魔方机器人开源 – Yangxx's Blog 说：

    2016/10/06 于 18:45

    [...] 关于这个方法，有大量的数学家和魔友们探索了很久，已有科学家证明三阶魔方最小还原步数为20步，即为上帝之数，意思是任意一个打乱的魔方20步以内都可以还原。我查阅了一些帖子、论坛，看到了很多方法，什么块构筑、niss等等，然而如果不花大量的时间学习还是不知所云。好吧，由于缺乏很多数学基础，例如群论一类的，自己搞一个算法出来还是比较困难，然而作为一个工程师而非科学家，实现业务需求才是最重要的，几经搜索，我找到了一个开源的最小步数解法，给出了C代码实现，而且我幸运的发现有国内的朋友已经把这个算法应用到了自己的DIY上，在此感谢动力老男孩 — http://www.diy-robots.com/?p=282。关于该算法的详细解释也在他的网站中有。 [...]

    回复
27. wyp 说：

    2016/11/28 于 07:27

    你好老男孩，下载你的源代码运行出现问题
    输入：FL DR BU BL FR UR BD FD UF LD RB LU FLL BLU LFU RUF FDR DBR URB BDL
    for (i = 0; i < 4; i++) corn2[i] = corn[4 + corn[i]];
    索引超出了数组界限。
    请赐教 谢谢

    回复
28. 六娃 说：

    2018/05/08 于 15:39

    准备把你翻译的算法用在一个js模拟出来的魔方上。。。所以要把你的改成js。。

    回复
29. fns 说：

    2018/07/13 于 22:05

    您好，我是有个问题实在弄不明白了，所以冒昧给您发微博。关于jaap的那个程序的问题。
    1.对于input 有些问题
    问题1：input 是否是根据自己魔方当前的状态输入的么？
    问题2：假设我想还原后的魔方F面是红色，u面是黄色，那么uF的块则为黄红。是否意味着对于当前魔方的状态，无论黄红的块在哪，他的标志就是UF?
    2.在jaap的源码里，对
    *order=”AECGBFDHIJKLMSNTROQP”,
    *bithash = “TdXhQaRbEFIJUZfijeYV”,
    等已经赋值了，是否需要根据当前我输入的魔方状态修改这些参数？

    回复
30. Dragon 说：

    2018/08/29 于 16:15

    好，UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR这段东西输入到命令行去他毫无反应，不知道是怎么回事

    回复