2012年8月6日星期一

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

首先, 我想说明下题目. 经过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)这三个循环的乘积; 类似的可得到其他基本操作的置换表示. 我们列举如下:
u=(1,2,3,4)(5,12,18,13)(9,17,16,6);
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);
b=(17,18,19,20)(2,16,23,11)(3,15,22,12);
r=(9,10,11,12)(5,21,20,2)(8,22,17,1);
l=(13,14,15,16)(3,6,24,19)(4,7,23,18);

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

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

  • mathematica:
    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:
    > 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:
    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下的验证代码:
> sg := permgroup(24, {f = [[5, 6, 7, 8], [1, 13, 24, 10], [4, 14, 21, 9]], 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]]});
> ordsg := grouporder(sg);

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


为此, 我们需要识别魔方上的颜色, 不妨假设还原状态下魔方上(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代码:
Stabchain = GroupStabilizerChain[RubikGroup2];
Stabchain /. gr_PermutationGroup :> GroupOrder[gr] // Column

可见, 魔方群的一个基是{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代码:
strongGS = GroupGenerators[Stabchain[[1, -1]]]

无论如何, 你可以通过直接观察, 得出我举的那个例子的置换是将:
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如下代码获得:
Clear[b, r];
iniorder = {
   R1, R2, R3, R4,
   G1, G2, G3, G4,
   B1, B2, B3, B4,
   b1, b2, b3, b4,
   g1, g2, g3, g4,
   r1, r2, r3, r4};
endorder = {
   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 = FindPermutation[iniorder, endorder]
GroupElementQ[RubikGroup2, rep]

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

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

GAP下对rep的分解


自由群的构造


建立以"u","d","f","b","r","l"为"字母"的自由群,
GAP代码:
freeg:=FreeGroup("u","d","f","b","r","l");;

群同态的建立


GAP代码:
hom:=GroupHomomorphismByImages(freeg,RubikGroup2,GeneratorsOfGroup(freeg),GeneratorsOfGroup(RubikGroup2));

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


以我举例的那个状态置换为例,
GAP代码:
rep:=(7, 22, 15)(11, 23, 24)(14, 20, 19);

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

GAP输出结果为:
d*b*u^-1*r*b^2*f^-1*r*f*r*u^-1*r^-1

这表明, 对魔方实行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

附记



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

    • (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可以由两个生成元生成:
    (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代码):
    iso:=IsomorphismFpGroup(RubikGroup2);

    得到一个同构表示(GAP输出):
    [ (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代码为:
     fp:=Image(iso);;
 RelatorsOfFpGroup(fp);

    GAP输出的抽象元之间的关系为:
    [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,是容易看出来的.
发帖者 时间：
标签：

没有评论:

发表评论

订阅： 博文评论 (Atom)