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

首先, 我想说明下题目. 经过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:
  • maple:
  • GAP:

于是, 可以利用上面的代码验证仅有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

附记

  • 文中那个强生成元的分解:
  • 文中的那个2阶魔方群RubikGroup2可以由两个生成元生成:
  • 我们也可以得到群的抽象表示(GAP代码):

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

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

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

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

发表评论