魔方还原(机械)算法初探

首先, 我想说明下题目. 经过3天的不断试验和思考, 我完全实现了二阶魔方的还原的机械算法. 换言之, 你可以一步一步地按照我说的算法还原二阶魔方. 基本想法是这样的, 首先将每个面编号(1,2,…,24), 那么现在任何一个转动都对应着(1,2,…24)的一个置换, 特别地, 我们可以写出6个基本操作的置换表示; 其次, 利用这六个置换表示生成2阶魔方群, 并利用GAP软件建立该群和由6个自由元生成的自由群的同态; 最后通过输入魔方的给定状态(即经过若干转动后得到的魔方)在该自由群下的生成元而得到具体的还原步骤. 下面让我详细叙述之, 并不时插入我陷入的误区. 你会看到还有许多未解决的问题(最短要多少步还原, 如何选取更优的生成元, 如何发现快速公式等), 但是并不是说不能通过我的方法还原.

魔方每个面的编号方法

为了简单起见, 我们把一条棱正对着自己, 而且编号从上, 到前, 再到右, 初始都是以上面的那个顶角块(即编号为1,5,9的块)开始的, 然后对前后右三个面以逆时针编号, 最后对面的编号用一个小括号区分.
最终的效果如图所示:

基本操作的置换表示

正如引言中提到的, 一旦编号了各个面, 那么每一个基本的操作都可以用一个置换来表示. 我们知道魔方的基本操作有对上(u), 下(d), 前(f), 后(b), 右(r), 左(l)各个面的旋转90度. 而且只需要逆时针旋转即可(顺时针可以通过逆时针三次得到); 可能有的人可能会认为只需由上,下,前这几种操作完成, 我们待会会看到(证明)这其实是不对的.
那么具体而言, 在上述编号下, 各个基本操作的置换表示是什么呢? 举例来说, u这个对顶面的逆时针旋转90度把1这个面变为2, 为了简便将其记为1->2, 同时有2->3, 3->4, 4->1; 在群论中, 我们习惯这个”循环”记为(1,2,3,4), 即它表示一个变换, 将1->2->3->4->1. 利用这个记号, 我们可以知道u=(1,2,3,4)(5,12,18,13)(9,17,16,6)这三个循环的乘积; 类似的可得到其他基本操作的置换表示. 我们列举如下:

利用该表示, 我们就可以得到由它们生成的群: RubikGroup2. 进而利用数学软件可以计算出它的阶是:88179840.

下面是它们在常用数学软件下的代码:

• mathematica:
  
  C

  u = Cycles[{{1, 2, 3, 4}, {5, 12, 18, 13}, {9, 17, 16, 6}}]; d = Cycles[{{21, 22, 23, 24}, {7, 10, 20, 15}, {8, 11, 19, 14}}]; f = Cycles[{{5, 6, 7, 8}, {1, 13, 24, 10}, {4, 14, 21, 9}}]; b = Cycles[{{17, 18, 19, 20}, {2, 16, 23, 11}, {3, 15, 22, 12}}]; r = Cycles[{{9, 10, 11, 12}, {5, 21, 20, 2}, {8, 22, 17, 1}}]; l = Cycles[{{13, 14, 15, 16}, {3, 6, 24, 19}, {4, 7, 23, 18}}]; RubikGroup2 = PermutationGroup[{r, d, f, b, r, l}]; GroupOrder[RubikGroup2]

  1 2 3 4 5 6 7 8

  u = Cycles[{{1, 2, 3, 4}, {5, 12, 18, 13}, {9, 17, 16, 6}}]; d = Cycles[{{21, 22, 23, 24}, {7, 10, 20, 15}, {8, 11, 19, 14}}]; f = Cycles[{{5, 6, 7, 8}, {1, 13, 24, 10}, {4, 14, 21, 9}}]; b = Cycles[{{17, 18, 19, 20}, {2, 16, 23, 11}, {3, 15, 22, 12}}]; r = Cycles[{{9, 10, 11, 12}, {5, 21, 20, 2}, {8, 22, 17, 1}}]; l = Cycles[{{13, 14, 15, 16}, {3, 6, 24, 19}, {4, 7, 23, 18}}]; RubikGroup2 = PermutationGroup[{r, d, f, b, r, l}]; GroupOrder[RubikGroup2]

• maple:
  
  C

  > with(group); > pg := permgroup(24, {b = [[17, 18, 19, 20], [2, 16, 23, 11], [3, 15, 22, 12]], d = [[21, 22, 23, 24], [7, 10, 20, 15], [8, 11, 19, 14]], f = [[5, 6, 7, 8], [1, 13, 24, 10], [4, 14, 21, 9]], l = [[13, 14, 15, 16], [3, 6, 24, 19], [4, 7, 23, 18]], r = [[9, 10, 11, 12], [5, 21, 20, 2], [8, 22, 17, 1]], u = [[1, 2, 3, 4], [5, 12, 18, 13], [9, 17, 16, 6]]}); > ordg := grouporder(pg);

  1 2 3

  > with(group); > pg := permgroup(24, {b = [[17, 18, 19, 20], [2, 16, 23, 11], [3, 15, 22, 12]], d = [[21, 22, 23, 24], [7, 10, 20, 15], [8, 11, 19, 14]], f = [[5, 6, 7, 8], [1, 13, 24, 10], [4, 14, 21, 9]], l = [[13, 14, 15, 16], [3, 6, 24, 19], [4, 7, 23, 18]], r = [[9, 10, 11, 12], [5, 21, 20, 2], [8, 22, 17, 1]], u = [[1, 2, 3, 4], [5, 12, 18, 13], [9, 17, 16, 6]]}); > ordg := grouporder(pg);

• GAP:
  
  C

  RubikGroup2:=Group((1,2,3,4)(5,12,18,13)(9,17,16,6),(21,22,23,24)(7,10,20,15)(8,11,19,14), (5,6,7,8)(1,13,24,10)(4,14,21,9),(17,18,19,20)(2,16,23,11)(3,15,22,12), (9,10,11,12)(5,21,20,2)(8,22,17,1),(13,14,15,16)(3,6,24,19)(4,7,23,18)); Size(RubikGroup2);

  1 2 3 4

  RubikGroup2:=Group((1,2,3,4)(5,12,18,13)(9,17,16,6),(21,22,23,24)(7,10,20,15)(8,11,19,14), (5,6,7,8)(1,13,24,10)(4,14,21,9),(17,18,19,20)(2,16,23,11)(3,15,22,12), (9,10,11,12)(5,21,20,2)(8,22,17,1),(13,14,15,16)(3,6,24,19)(4,7,23,18)); Size(RubikGroup2);

于是, 可以利用上面的代码验证仅有u, f, r 三种基本操作生成的群的阶是3674160, 于是与原来的2阶魔方群不同构.
这里, 我只给出maple下的验证代码:

通过颜色寻求从初始状态变换到给定状态的置换

为此, 我们需要识别魔方上的颜色, 不妨假设还原状态下魔方上(u), 前(f), 右(r)的颜色分别是红(R), 绿(G), 黑(B), 而且其对立面的颜色用小写字母表示. 如图所示:

那么, 从理论上说, 我们可以通过对给定状态颜色的编号序列得出该状态的置换表示, 例如:初始状态下各个面的颜色按照编号顺次是:R,R,R,R,G,G,G,G,B,B,B,B,b,b,b,b,g,g,g,g,r,r,r,r; 而给定状态的颜色按照编号顺序依次是:R,R,R,R,G,G,b,G,B,B,r,B,b,g,r,b,g,g,g,b,r,G,B,r; 那么我们要求计算出从初始状态(各面同色)到给定状态的置换(它是一系列u,d,f,b,r,l的复合). 注意到这时我们应该在魔方群中去找(比较难), 不能在24阶置换群中去找(容易). 其实通过所谓的强生成集, 我们可以很容易找到该置换, 但是我还没学会. (注意很多软件都可以算出稳定链以及基, 于是这种方法是可行的). 我这里先给出计算强生成集以及稳定链的mathematica代码:

可见, 魔方群的一个基是{1, 2, 3, 7, 4, 8, 11}, 与之相对的强生成元是:
{(11, 20, 22)(15, 19, 23),
(11, 23)(15, 22)(19, 20),
(8, 21, 10)(11, 22, 20)(15, 19, 23),
(8, 20, 19)(10, 22, 15)(11, 23, 21),
(4, 15, 6, 23, 13, 19)(8, 22, 21, 20, 10, 11),
(7, 10, 20, 15)(8, 11, 19, 14)(21, 22, 23, 24),
(3, 6, 24, 19)(4, 7, 23, 18)(13, 14, 15, 16),
(2, 16, 23, 11)(3, 15, 22, 12)(17, 18, 19, 20),
(1, 13, 24, 10)(4, 14, 21, 9)(5, 6, 7, 8)}
得到强生成元的mathematica代码:

无论如何, 你可以通过直接观察, 得出我举的那个例子的置换是将:
R1, R2, R3, R4,
G1, G2, G3, G4,
B1, B2, B3, B4,
b1, b2, b3, b4,
g1, g2, g3, g4,
r1, r2, r3, r4
变为
R1, R2, R3, R4,
G1, G2, b3, G4,
B1, B2, r4, B4,
b1, g3, r2, b4,
g1, g2, g4, b2,
r1, G3, B3, r3.
于是得到该状态的置换(rep)是:
(7, 22, 15)(11, 23, 24)(14, 20, 19),
可以利用mathematica如下代码获得:

最后一行是测试是不是魔方群中的一个元素(就是这个测试使得我发现我原来的置换是在$S_{24}$里面做的);

至此, 我们已经把问题转化为把rep这个状态置换用u,d,f,b,r,l及它们各自的逆具体地表示出来. 为此, 我们需要借助自由群以及有限群论计算软件GAP.

GAP下对rep的分解

自由群的构造

建立以”u”,”d”,”f”,”b”,”r”,”l”为”字母”的自由群,
GAP代码:

群同态的建立

GAP代码:

将状态置换分解为基本操作(一个具体的元素分解为生成元的乘积)

以我举例的那个状态置换为例,
GAP代码:

最后把这个元素(rep)分解为基本操作的乘积:
GAP代码:

GAP输出结果为:

这表明, 对魔方实行rep的逆就可以还原魔方了. 即依次进行r,u,r逆,f逆,b,b,r逆,u,b逆,d逆.
其中, 如前所假设(注意魔方的放置应和第一个图一致), r表示右方的面逆时针旋转90度, u表示上方的面逆转90度, 同理有其他的字母, 而r逆当然就是表示右方的面顺时针旋转90度, 其他类似得到.

一些思考

本探索实现了将一个2阶魔方的任一状态还原的步骤(分解为基本操作及其逆的乘积), 但是还有如下几点没有解决:

1. 本算法很可能不是最优的, 即不是把给定状态还原为初始状态所需的最少的步骤;
2. 如何改造变生成元, 使其能在大多数情形下更快的完成还原
3. 对RubkiGroup2的阶进行素因数分解可以知道它有5阶元和7阶元, 是否有这两个元扩充成生成元会比原来的6种基本操作更优.
4. 如何用强生成元来获得状态置换的表示?

参考文献

1. Factorization in finite Groups

附记

• 文中那个强生成元的分解:
C

(11, 20, 22)(15, 19, 23)=f*b^-1*l^-1*f^-2*r^2*f*u^-1*f^-1*r*f*u^-1*r*u^-1*f*u^-1*f^-1*u*r^-1 (11, 23)(15, 22)(19, 20)=r^-1*f^-1*u*l*b*r*d^-1*u*b^-1*u*r*u^-1*r^-1*d^-1*u*r^-1*d*r^-1*b*r*b^-1*u*f^-1*r^-2*f*b (8, 21, 10)(11, 22, 20)(15, 19, 23)=r*b*u^-1*r*b^2*f^-1*r*f*r^-1*f*u*f^-1*u^-1*f^-1*u*b*u^-1*f*u*b^-1*u^-1*r*u^-1*f*u*f^-1*u*r^-1*u*f^-1*r^-1*f*u^-1 (8, 20, 19)(10, 22, 15)(11, 23, 21)=u*f^-1*r*f*u^-1*r*u^-1*f*u^-1*f^-1*u*r^-1*b*u^-1*b^-1*r*u*r^-1*u*f^-1*r^-2*f*b^-2*r^-2*b^-1 (4, 15, 6, 23, 13, 19)(8, 22, 21, 20, 10, 11)=u*r*u^-1*r^-1*b*u*b^-1*f^-1*r^-1*f*u^-1*f*l*f^-1*u*r (7, 10, 20, 15)(8, 11, 19, 14)(21, 22, 23, 24)=d (3, 6, 24, 19)(4, 7, 23, 18)(13, 14, 15, 16)=l (2, 16, 23, 11)(3, 15, 22, 12)(17, 18, 19, 20)=b (1, 13, 24, 10)(4, 14, 21, 9)(5, 6, 7, 8)=f

1 2 3 4 5 6 7 8 9

(11, 20, 22)(15, 19, 23)=f*b^-1*l^-1*f^-2*r^2*f*u^-1*f^-1*r*f*u^-1*r*u^-1*f*u^-1*f^-1*u*r^-1 (11, 23)(15, 22)(19, 20)=r^-1*f^-1*u*l*b*r*d^-1*u*b^-1*u*r*u^-1*r^-1*d^-1*u*r^-1*d*r^-1*b*r*b^-1*u*f^-1*r^-2*f*b (8, 21, 10)(11, 22, 20)(15, 19, 23)=r*b*u^-1*r*b^2*f^-1*r*f*r^-1*f*u*f^-1*u^-1*f^-1*u*b*u^-1*f*u*b^-1*u^-1*r*u^-1*f*u*f^-1*u*r^-1*u*f^-1*r^-1*f*u^-1 (8, 20, 19)(10, 22, 15)(11, 23, 21)=u*f^-1*r*f*u^-1*r*u^-1*f*u^-1*f^-1*u*r^-1*b*u^-1*b^-1*r*u*r^-1*u*f^-1*r^-2*f*b^-2*r^-2*b^-1 (4, 15, 6, 23, 13, 19)(8, 22, 21, 20, 10, 11)=u*r*u^-1*r^-1*b*u*b^-1*f^-1*r^-1*f*u^-1*f*l*f^-1*u*r (7, 10, 20, 15)(8, 11, 19, 14)(21, 22, 23, 24)=d (3, 6, 24, 19)(4, 7, 23, 18)(13, 14, 15, 16)=l (2, 16, 23, 11)(3, 15, 22, 12)(17, 18, 19, 20)=b (1, 13, 24, 10)(4, 14, 21, 9)(5, 6, 7, 8)=f

• 文中的那个2阶魔方群RubikGroup2可以由两个生成元生成:
  
  C

  (2,24,21,13,19,16,20)(3,11,12,7,10,6,23)(4,15,18,22,17,14,8)=r^2*u^-1*r^-1*f*u^-1*f^-1*r*u*r^-1*f^-1*r^-1*u*r*d^-1*b*r^-1*b^-1*u^-1*b^-2*u^-2*r^-1*u^-1*d (1,10,9,21,5,8)(2,3,23,13,11)(4,20,17,16,19)(6,22,12, 18,15)(7,14,24) =r^-1*f^-1*u*l*b*r*d^-1*u*b^-1*u*r*u^-1*r^-1*u*r*u^-1*r^-1*b*u*b^-1*f^-1*r*f*u^-1*r*u^-1*r^-1*f*d^-1*f^-1*l*r^-1*u*b^ -1*r^-1*f*d^-1

  1 2 3

  (2,24,21,13,19,16,20)(3,11,12,7,10,6,23)(4,15,18,22,17,14,8)=r^2*u^-1*r^-1*f*u^-1*f^-1*r*u*r^-1*f^-1*r^-1*u*r*d^-1*b*r^-1*b^-1*u^-1*b^-2*u^-2*r^-1*u^-1*d (1,10,9,21,5,8)(2,3,23,13,11)(4,20,17,16,19)(6,22,12, 18,15)(7,14,24) =r^-1*f^-1*u*l*b*r*d^-1*u*b^-1*u*r*u^-1*r^-1*u*r*u^-1*r^-1*b*u*b^-1*f^-1*r*f*u^-1*r*u^-1*r^-1*f*d^-1*f^-1*l*r^-1*u*b^ -1*r^-1*f*d^-1

• 我们也可以得到群的抽象表示(GAP代码):
  
  C

  iso:=IsomorphismFpGroup(RubikGroup2);

  1	iso:=IsomorphismFpGroup(RubikGroup2);

  
  得到一个同构表示(GAP输出):
  
  C

  [ (11,19)(15,20)(22,23), (1,2,3,4,7,8,15)(5,12,18,13,14,21,19)(6,24,10,23,9,17,16), (1,2,3,4,7,11,15)(5,12,18,13,14, 22,19)(6,24,20,23,9,17,16), (11,22,20)(15,23,19), (1,9,5)(15,19,23), (2,17,12)(15,19,23), (3,18,16)(15,23,19), (4,13,6)(15,23,19), (7,24,14)(15,19,23), (8,21,10)(15,23,19) ] -> [ F1, F2, F3, F4, F5, F6, F7, F8, F9, F10 ]

  1 2 3

  [ (11,19)(15,20)(22,23), (1,2,3,4,7,8,15)(5,12,18,13,14,21,19)(6,24,10,23,9,17,16), (1,2,3,4,7,11,15)(5,12,18,13,14,     22,19)(6,24,20,23,9,17,16), (11,22,20)(15,23,19), (1,9,5)(15,19,23), (2,17,12)(15,19,23), (3,18,16)(15,23,19),   (4,13,6)(15,23,19), (7,24,14)(15,19,23), (8,21,10)(15,23,19) ] -> [ F1, F2, F3, F4, F5, F6, F7, F8, F9, F10 ]

  
  利用该同构表示, 我们可以得到2阶魔方群的抽象关系(用F1…F10来表示), GAP代码为:
  
  C

  fp:=Image(iso);; RelatorsOfFpGroup(fp);

  1 2	fp:=Image(iso);; RelatorsOfFpGroup(fp);

  
  GAP输出的抽象元之间的关系为:
  
  C

  [F1^2, F1^-1*F2*F1*F2^-1*F3^-1*F2*F10^-2*F4^-1, F1^-1*F3*F1*F3*F2^-1*F3^-2*F2^2*F3*F2^-2*F3*F2^-1*F9^-2*F4^-1, F2^7*F3^-7, F2^7*F3^-1*F2^-1*F3^-1*F2^-1*F3^-1*F2^-1*F3^-1*F2^-1, F2^-1*F3^-1*F2*F3*F2^-1*F3^-1*F2*F3, F2^-2*F3^-1*F2*F3^2*F2^-2*F3^-1*F2*F3^2, F2^-3*F3^-1*F2*F3^3*F2^-3*F3^-1*F2*F3^3, F1^-1*F4*F1*F4^-2, F1^-1*F5*F1*F5^-1*F4^-1, F1^-1*F6*F1*F6^-1*F4^-1, F1^-1*F7*F1*F7^-1*F4^-2, F1^-1*F8*F1*F8^-1*F4^-2, F1^-1*F9*F1*F9^-1*F4^-1, F1^-1*F10*F1*F10^-1*F4^-2, F2^-1*F4*F2*F5^-1*F4^-1, F2^-1*F5*F2*F6^-1*F5^-2, F2^-1*F6*F2*F7^-2*F5^-2, F2^-1*F7*F2*F8^-1*F5^-1, F2^-1*F8*F2*F9^-2*F5^-1, F2^-1*F9*F2*F10^-2*F5^-2, F2^-1*F10*F2*F5^-1, F3^-1*F4*F3*F5^-1, F3^-1*F5*F3*F6^-1*F5^-2, F3^-1*F6*F3*F7^-2*F5^-2, F3^-1*F7*F3*F8^-1*F5^-1, F3^-1*F8*F3*F9^-2*F5^-1, F3^-1*F9*F3*F5^-2*F4^-2, F3^-1*F10*F3*F10^-1*F5^-1, F4^3, F5^3, F5^-1*F4^-1*F5*F4, F6^3, F6^-1*F4^-1*F6*F4, F6^-1*F5^-1*F6*F5, F7^3, F7^-1*F4^-1*F7*F4, F7^-1*F5^-1*F7*F5, F7^-1*F6^-1*F7*F6, F8^3, F8^-1*F4^-1*F8*F4, F8^-1*F5^-1*F8*F5, F8^-1*F6^-1*F8*F6, F8^-1*F7^-1*F8*F7, F9^3, F9^-1*F4^-1*F9*F4, F9^-1*F5^-1*F9*F5, F9^-1*F6^-1*F9*F6, F9^-1*F7^-1*F9*F7, F9^-1*F8^-1*F9*F8, F10^3, F10^-1*F4^-1*F10*F4, F10^-1*F5^-1*F10*F5, F10^-1*F6^-1*F10*F6, F10^-1*F7^-1*F10*F7, F10^-1*F8^-1*F10*F8, F10^-1*F9^-1*F10*F9]

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

  [F1^2, F1^-1*F2*F1*F2^-1*F3^-1*F2*F10^-2*F4^-1, F1^-1*F3*F1*F3*F2^-1*F3^-2*F2^2*F3*F2^-2*F3*F2^-1*F9^-2*F4^-1,   F2^7*F3^-7, F2^7*F3^-1*F2^-1*F3^-1*F2^-1*F3^-1*F2^-1*F3^-1*F2^-1, F2^-1*F3^-1*F2*F3*F2^-1*F3^-1*F2*F3,   F2^-2*F3^-1*F2*F3^2*F2^-2*F3^-1*F2*F3^2, F2^-3*F3^-1*F2*F3^3*F2^-3*F3^-1*F2*F3^3, F1^-1*F4*F1*F4^-2,   F1^-1*F5*F1*F5^-1*F4^-1, F1^-1*F6*F1*F6^-1*F4^-1, F1^-1*F7*F1*F7^-1*F4^-2, F1^-1*F8*F1*F8^-1*F4^-2,   F1^-1*F9*F1*F9^-1*F4^-1, F1^-1*F10*F1*F10^-1*F4^-2, F2^-1*F4*F2*F5^-1*F4^-1, F2^-1*F5*F2*F6^-1*F5^-2,   F2^-1*F6*F2*F7^-2*F5^-2, F2^-1*F7*F2*F8^-1*F5^-1, F2^-1*F8*F2*F9^-2*F5^-1, F2^-1*F9*F2*F10^-2*F5^-2,   F2^-1*F10*F2*F5^-1, F3^-1*F4*F3*F5^-1, F3^-1*F5*F3*F6^-1*F5^-2, F3^-1*F6*F3*F7^-2*F5^-2, F3^-1*F7*F3*F8^-1*F5^-1,   F3^-1*F8*F3*F9^-2*F5^-1, F3^-1*F9*F3*F5^-2*F4^-2, F3^-1*F10*F3*F10^-1*F5^-1, F4^3, F5^3, F5^-1*F4^-1*F5*F4, F6^3,   F6^-1*F4^-1*F6*F4, F6^-1*F5^-1*F6*F5, F7^3, F7^-1*F4^-1*F7*F4, F7^-1*F5^-1*F7*F5, F7^-1*F6^-1*F7*F6, F8^3,   F8^-1*F4^-1*F8*F4, F8^-1*F5^-1*F8*F5, F8^-1*F6^-1*F8*F6, F8^-1*F7^-1*F8*F7, F9^3, F9^-1*F4^-1*F9*F4,   F9^-1*F5^-1*F9*F5, F9^-1*F6^-1*F9*F6, F9^-1*F7^-1*F9*F7, F9^-1*F8^-1*F9*F8, F10^3, F10^-1*F4^-1*F10*F4,   F10^-1*F5^-1*F10*F5, F10^-1*F6^-1*F10*F6, F10^-1*F7^-1*F10*F7, F10^-1*F8^-1*F10*F8, F10^-1*F9^-1*F10*F9]

  
  每一个都是恒等元, 例如第一个F1^2=id,是容易看出来的.