解魔方的机器人攻略17 – 魔方CFOP算法

本来我想把这个攻略做成一个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入门解法

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

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,我用的是第二名的算法。



对 “解魔方的机器人攻略17 – 魔方CFOP算法” 的 18 条 评论

  1. dot 说:

    惊讶,沙发

  2. cb观光团 说:

    跟住 好好学学

  3. 刘磊 说:

    非常感谢前辈能共享出来这样伟大而又实用的教程。
    人工智能和机器人一直是我的梦想,可是一直以来自己被懒惰和工作浪费了太多精力,而一直将此束之高阁。
    待过了这好多年,才发现岁月匆匆,而自己却毫无成就,难免黯然悔恨。
    现在终于决定奋发图强,实现自己的梦想,更希望能去日本深造。
    前辈的作品给予了我很大的启示和鼓励,谢谢。

  4. btyytt 说:

    罪过啊, 当时想了解莫非C#可以用来操作那个主机 -_-#.

  5. yfeng 说:

    博主什么时候出个Microsoft Robotics Studio开发的教程啊,严重期待中。

  6. Snake 说:

    今天已经买了机器人了,白天跟你发了EMAIL的,我的是封三,喜欢魔方很久了,大概三个月吧(哈哈,别拍砖,只有3个月,但是很喜欢)。因为自己没什么本事(CFOP不熟,还原平均1分20秒),所以打算做个会魔方的机器人,看看能不能比我快。。

  7. 娘子 说:

    to Snake:
    魔方转的再快也很难超越人手,毕竟人手的灵活度比起魔方,高级的不是一点半点。3个月转到1分20秒已经很好了:)

  8. lemon 说:

    哥的rss订不了,nandao我菜

    • Snake 说:

      应该是可以订的,不知道你是什么阅读器,我用M8上的阅读器订阅是成功的

  9. wordpress的rss设置好像有点问题,不过上面的地址我用抓虾试过是可以的

  10. wsj 说:

    代码上把其他的也加上呀,好麻烦

  11. todd 说:

    这个代码直接运行会抛异常?

    我把 arColor 这几个数组的大小都设为了5000,还是异常

    Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 5000
    at CFOP$Steps.AddStep(CFOP.java:1065)
    at CFOP.SecondLayer(CFOP.java:359)

    • 我这里没有检查输入数据,所以如果输入的数据有问题的话,估计是算不出结果

      • 蔡通达 说:

        坑爹!算法源码根本就是错的!

        • 在其他地方说明过很多次了,这些代码在我的NXT里都是曾经跑过并能运行的。
          但是现在leJOS都已经升级很多版了,你还指望代码能直接编译运行吗?但是你只要花几分钟看看错误,基本都是函数过期,换成最新版本得对应函数就可以了。
          你就是抄作业,也得改个名字吧

  12. kongjiazhen 说:

    动力大哥,看了的cfop java程序后表示看不太懂,你能都为这个程序写一下详细的注释呢?相信很多人都期待能看懂大哥写的程序。期待中。。。

    • cfop的程序实际上是根据魔方的cfop玩法写的,所以在此之前,你需要先知道cfop是怎么玩的。
      然后其实就是无数的if-else加坐标变换了

  13. [...] 呵呵,其实这个网站是一群魔方爱好者比赛的网站,上面的链接直接给出了比赛结果,我选了第三个算法。而这个算法已经有朋友从c写成了c#,于是我就下载了c#的代码,稍微改动了下,改成了Java版(这真是。。。哈哈)。这位朋友的站点地址如下:http://www.diy-robots.com 动力老男孩的博客。里面除了魔方,还有很多有意思的东西哦比如自制盗梦陀螺,四轴飞行器等等~ [...]

发表评论

可以使用下列 XHTML 标签:<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>