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

### 基本操作的置换表示

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);

• 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);

> 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);

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

Stabchain = GroupStabilizerChain[RubikGroup2];
Stabchain /. gr_PermutationGroup :> GroupOrder[gr] // Column

{(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)}

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.

(7, 22, 15)(11, 23, 24)(14, 20, 19),

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]

### GAP下对rep的分解

#### 自由群的构造

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);

GAP代码:

w:=PreImagesRepresentative(hom,rep);

GAP输出结果为:

d*b*u^-1*r*b^2*f^-1*r*f*r*u^-1*r^-1

### 一些思考

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

### 附记

• 文中那个强生成元的分解:
• (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,是容易看出来的.