解魔方机器人[五]-植入算法

到此为止,魔方的扫描与计算机表示都已经完成,解决步骤的算法实现,应该说与EV3传感器和马达没有太多的关系,主要是由计算机完成的。魔方的解决是基于群论实现的,说实话我本人并没有对这种理论算法做进一步深入的研究,因为他确实需要时间去学习。好在一些网站早已经将这部分算法实现,并开源出来。Tomas Rokicki的个人主页包含了大量的算法和程序实现,感兴趣的同学强烈推荐:http://tomas.rokicki.com/

5.1 算法程序编译与使用

Tomas Rokicki曾发起过一次解魔方编程活动,所有参赛的程序都是开源的。同样,感兴趣研究魔方算法的同学可以自行围观:http://tomas.rokicki.com/cubecontest/winners.html

如前所述,我只是需要在EV3中使用这些程序,下载其中一个代码,然后按照代码所使用的编程语言进行编译,即可得到可执行的文件。

在此我使用页面中排名第2的程序(pochmann),作者使用C++,因此我们使用C++编译器将代码编译为可执行程序。以g++编译器为例,执行:

g++ JohnnyX.cpp -o pochmann.exe

所获得的pochmann.exe即为解魔方算法的可执行文件。参照这个程序的使用说明,程序的使用方法是:

  • 输入:可执行文件 魔方的状态表示
  • 输出:魔方的解法

新的问题出现了,程序输入中的魔方的状态表示是什么样的?跟我们在上一章整理的表达式有什么关系吗?

5.2 魔方色块表示法

先来看个结论,采用色块表示法,一个还原的魔方可表示为:

UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

不要被这个东西吓到,我们慢慢来看,就会发现并没有那么难。

字母含义

这一串字符中,一共包含了6个字母:U F R B L D,分别代表了一个魔方的上面(Up)、前面(Front)、右面(Right)、后面(Back)、左面(Left)、底面(Down)

魔方的轴

也许你会发现一个问题,就是用这6个字母表示魔方的6个面,如果魔方变换了方位那6个面的方向不是也变了?这就需要说明一下魔方的轴。

如果你手边有一个魔方,那么仔细注意魔方6个面的中心点,然后保持中心点的方向不动,试着去转动6个面,你一定会发现,无论你怎么转动这些面,这6个中心点的位置是不会发生变化的。

比如下面这两幅图:打乱前和打乱后,白色、绿色、红色面的中心点并未变化。也即魔方的轴在拧魔方的过程中,相对位置是不会发生变化的。

还原状态

还原状态

打乱状态

打乱状态

魔方的色块

魔方由8个角块、12个棱块和6个中心块组成。中心块的位置固定在十字架上。每个角块3面有颜色、每个棱块2面有颜色、每个中心块1面有颜色。

cube block

由于中心块的相对位置不变,对于角块和棱块可以用每个面所属的方向进行描述。依然,一个还原的魔方棱块和角块可以表示为:

  • 棱块 UF UR UB UL DF DR DB DL FR FL BR BL
  • 角块 UFR URB UBL ULF DRF DFL DLB DBR

新的问题又来了,一个打乱的魔方怎么表示?

打乱魔方的色块表示

首先我们还是来看那个还原的魔方表示:

UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

现在已经知道了那么表示棱块和角块,但其实这个表示是包含两个隐含属性的,分别是:色块位置、颜色方向

  • 色块位置 UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
  • 颜色方向 UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

色块位置很好理解,正如前文所述,就是每个色块位置的方向型表示。而颜色方向可以理解为,色块某一面的颜色与某个中心色块颜色相同,那么这个色块某一面的颜色所属方向,即为那个中心色块颜色的方向。

比如,在下面这个魔方里面,位置处于FR的色块,色块的F面是红色、R面是蓝色,分别与魔方F面和U面的中心点的颜色一样,所以这个色块的颜色方向为:FU。

色块表示

色块表示

如果理解了上面这个例子,那么再来看色块位置和颜色方向两行的表示,可以说角块的表示方法只是按照“颜色方向”对魔方进行描述,而描述的顺序是按照“色块位置”执行的。

5.3 程序设计

# 将6x9个面的表示转换为12+8个色块的表示
#                   +--5U-+
#                   |0 1 2|
#                   |3 4 5|
#                   |6 7 8|
# +--0F-+--1R-+--2B-+--3L-+
# |0 1 2|0 1 2|0 1 2|0 1 2|
# |3 4 5|3 4 5|3 4 5|3 4 5|
# |6 7 8|6 7 8|6 7 8|6 7 8|
# +-----+-----+-----+--4D-+
#                   |0 1 2|
#                   |3 4 5|
#                   |6 7 8|
#                   +-----+
# 输入:6x9个面的表示法
# 输出:12+8个块的表示法

def cvt2reid(orignal):
  c = str(orignal)

  # 各个面的中心块代表该面的颜色方向
  c2r = {c[5][4]:'U', c[0][4]:'F', c[1][4]:'R', c[2][4]:'B', c[3][4]:'L', c[4][4]:'D'}

  # 按照指定规律进行色块组合
  reid_mode = c2r[c[5][5]]+c2r[c[0][1]]+' '+c2r[c[5][1]]+c2r[c[1][1]]+' '+c2r[c[5][3]]+c2r[c[2][1]]+' '+c2r[c[5][7]]+c2r[c[3][1]]+' '+\
              c2r[c[4][5]]+c2r[c[0][7]]+' '+c2r[c[4][7]]+c2r[c[1][7]]+' '+c2r[c[4][3]]+c2r[c[2][7]]+' '+c2r[c[4][1]]+c2r[c[3][7]]+' '+\
              c2r[c[0][5]]+c2r[c[1][3]]+' '+c2r[c[0][3]]+c2r[c[3][5]]+' '+c2r[c[2][3]]+c2r[c[1][5]]+' '+c2r[c[2][5]]+c2r[c[3][3]]+' '+\
              c2r[c[5][2]]+c2r[c[0][2]]+c2r[c[1][0]]+' '+c2r[c[5][0]]+c2r[c[1][2]]+c2r[c[2][0]]+' '+\
              c2r[c[5][6]]+c2r[c[2][2]]+c2r[c[3][0]]+' '+c2r[c[5][8]]+c2r[c[3][2]]+c2r[c[0][0]]+' '+\
              c2r[c[4][8]]+c2r[c[1][6]]+c2r[c[0][8]]+' '+c2r[c[4][2]]+c2r[c[0][6]]+c2r[c[3][8]]+' '+\
              c2r[c[4][0]]+c2r[c[3][6]]+c2r[c[2][8]]+' '+c2r[c[4][6]]+c2r[c[2][6]]+c2r[c[1][8]]

  # 返回色块表示列表
  return reid_mode

# 借助编译好的解魔方可执行文件,完成魔方还原步骤
# 此处使用pochmann提供的解决方法
def cube_algorithm(cube_unsolved):
  cube_solved = os.popen('pochmann.exe '+cube_unsolved).readline()
	
  # 返回还原魔方的步骤
  return cube_solved

发表评论

电子邮件地址不会被公开。 必填项已用*标注