魔方的数学结构:置换、群与状态图

看到一段把魔方表示成三组圆环的动画,我想弄清两个问题:那些圆点为什么能够代替魔方上的色块?理解这种表示,是否就能理解怎样复原魔方?这篇笔记从群论和魔方的基础开始,逐步走到置换、交换子与最短路径。[1]

魔方与三组圆环并排展示的动画截图

一、群论基础

集合、映射与置换

集合是一组对象。例如, P={1,2,3,4} 是四个编号组成的集合。映射 f:P→P 为每个输入指定唯一的输出。写成 f(1)=3 ,意思是把编号 1 送到编号 3。

如果不同输入不会送到同一个输出,并且每个输出都有输入与之对应,这个映射就是双射。对有限集合而言,双射把所有对象重新安排一遍,既没有重复,也没有遗漏。一个集合到自身的双射称为置换。把四张有编号的卡片重新排列,就是一个例子。

为什么强调双射?因为每个输出都能唯一地追溯到原来的输入。于是这个操作可以撤销。将卡片合并、丢弃或复制,都失去了这种可逆性。

操作的复合

“运算”不只指数字的加法或乘法。先做一个动作 a ,再做另一个动作 b ,也可以合成一个新动作,记为 a∗b 。例如,先把正方形顺时针转 90∘ ,再转 180∘ ,整体效果等于顺时针转 270∘ 。

后文省略乘号,写 ab 表示“先做 a ,再做 b ”。这是本文对动作串的统一约定。它与很多教材中普通函数复合的记号不同: f∘g 通常表示先做 g ,再做 f 。读公式时要辨认使用的是哪一种记法。

相同的整体效果视为同一个操作。转一整圈与完全不转,对正方形四个顶点的最终位置没有区别;群论在这里比较最终作用,而不记录手走过的轨迹。

群的定义与公理

设 G 是一组操作, ∗ 是组合这些操作的运算。如果满足下面的条件, (G,∗) 就构成一个群。这些条件都对集合中的任意元素成立。[2]

封闭性:做完集合中的两个操作,得到的整体操作仍属于这个集合。

a,b∈G⟹a∗b∈G.

结合律:连续做三件事,可以先把前两件看作整体,也可以先把后两件看作整体。

(a∗b)∗c=a∗(b∗c).

这里没有交换动作的先后,只改变了分组方式。

单位元:存在一个“不改变结果”的操作 e ,放在任一操作前后都不影响它。

e∗a=a∗e=a.

逆元:每个操作 a 都有一个撤销它的操作 a−1 。

a∗a−1=a−1∗a=e.

有些教材把封闭性包含在“二元运算”的定义中,因此只另列三条公理,内容相同。群的定义不要求交换律 a∗b=b∗a 。结合律讨论括号,交换律讨论顺序,二者是不同的问题。

正方形旋转与循环群

给正方形的四个顶点贴上 A、B、C、D。只允许绕中心旋转整数个 90∘ ,令 r 表示顺时针转一次,便得到

C4={e,r,r2,r3},r4=e.

指数表示重复次数, r2=rr ; r0=e 。两次旋转组合时,把指数相加,超过一整圈的部分可以去掉。

rarb=r(a+b)mod4.

“模 4”就是除以 4 后保留余数,例如 5mod4=1 ,所以 r3r2=r 。因为 rr3=r4=e , r 的逆元是 r3 ; r2 则是自己的逆元。这个例子满足交换律,但不能由此推断其他群也满足。

试着正转四次,或者正转一次再逆转一次。比较顶点标记,而不只看正方形的外轮廓。

正方形旋转与循环群 C₄

置换的循环分解

循环 (1 2 3 4) 表示一个同步操作: 1→2 、 2→3 、 3→4 、 4→1 。它不是让四个对象轮流行动的四步指令。反向沿循环走,就得到逆置换 (1 4 3 2) 。

一个置换可能包含多个互不相交的循环。例如 (1 2)(3 4 5) 同时交换 1、2,并让 3、4、5 循环。由于操作的对象互不重叠,这两个循环可交换执行顺序;有重叠的循环则一般不能。

任何有限置换都可以这样分解。方法是从一个编号出发,反复追踪它被送到哪里,直到回到起点;再从一个尚未访问的编号开始。没有移动的编号是长度为 1 的循环,通常省略。

群的基本概念与排列奇偶性

群的阶 |G| 是群中元素的数量。元素的阶 ord(a) 是使 ak=e 成立的最小正整数 k 。在 C4 中,群的阶为 4,但元素 r2 的阶为 2。对互不相交的循环,要让它们同时归位,重复次数必须是所有循环长度的公倍数,因此置换的阶等于这些长度的最小公倍数。

能通过反复组合及取逆产生全部操作的一组元素,称为生成元。记号 ⟨r⟩=C4 表示由 r 生成整个旋转群。若从一个群中选出的部分元素,在原运算下仍构成群,就称为子群。例如 {e,r2} 是 C4 的子群。

n 个不同对象的全部置换构成对称群 Sn 。第一个位置有 n 种选择,第二个有 n−1 种,依次相乘,得到它的阶

|Sn|=n!=n(n−1)⋯2⋅1.

最后介绍一个判断排列是否合法的工具。只交换两个对象称为对换。任何置换都能分解成对换;虽然分解方式不唯一,对换次数的奇偶性却保持一致,因此可以区分偶排列与奇排列。用符号 sgn(π) 表示,偶排列为 +1 ,奇排列为 −1 ,组合时两者的符号相乘。[3]

长度为 k 的循环可分解成 k−1 次对换,所以

sgn(k-循环)=(−1)k−1.

例如 4-循环是奇排列,3-循环是偶排列;两个奇排列组合后是偶排列。后面魔方的一个重要限制就来自这条规则。

二、三阶魔方的结构与表示

小块、贴纸与状态

三阶魔方的外观是每面 3×3 格,共六个面。但学习它的规则时,应先辨认实际一起运动的小块。

小块 个数 每块的贴纸数 需要追踪的信息
中心块 6 1 给六个面提供参考颜色
棱块 12 2 位置和翻转方向
角块 8 3 位置和扭转方向

因此贴纸总数为 6+12×2+8×3=54 。例如,白红绿角块上的三张贴纸属于同一块塑料,任何转动都必须带着它们一起走。它们不能像三张独立卡片那样自由排列。[4]

贴纸是可以被跟踪的对象,贴纸位置是某一面上的固定格子。白色贴纸可以从上面移到前面,但“上面左上角”这个位置的定义不变。整个状态则必须记录所有小块的位置及方向,不能只描述某一张贴纸。

小块的位置与方向

棱块占据一个位置时有两种方向。比如白红棱块即使回到了白、红两中心之间,也可能把白色朝向红面、红色朝向白面,这叫翻转。

角块在一个角位置有三种方向。白红绿角块可以绕自身的角方向扭转 120∘ ,仍占据原来的位置,却让三张贴纸分别朝向错误的面。

因此复原需要同时满足两件事:块的位置正确,块的方向也正确。本文讨论常见的纯色三阶魔方,不计中心贴纸上的箭头、文字或图案是否转正。

参照系与转动记号

固定一套观察方向:上白、下黄、前绿、后蓝、右红、左橙。相对面分别是白/黄、绿/蓝、红/橙。中心块给出这套坐标,在本文的模型中保持固定。

面 上 下 右 左 前 后
记号 U D R L F B

单独一个字母表示该面顺时针转 90∘ ,撇号表示逆时针 90∘ ,后缀 2 表示转 180∘ 。例如 R' 是右面逆转,U2 是上面半转。顺时针必须从所转面的外侧、正对那个面判断,背面和底面也遵守同一规则。[5]

转一个外层,会同时带动四个角块、四个棱块,以及该面的中心朝向;纯色中心本身的位置不变。本文只开放这六个外层的转动。整体拿起魔方换方向属于改变观察坐标,暂不作为新的打乱状态。

三、魔方群与操作复合

把六种基本面转动、它们的逆操作,以及任意有限次组合得到的操作放在一起,定义

G=⟨U,D,R,L,F,B⟩.

封闭性在定义中已经包含:两串合法转动接起来,仍是一串合法转动。结合律来自操作复合,三串动作的分组不影响实际执行顺序。空动作是单位元 e 。每一步都能反向转回去,整个序列也有逆元,因此这些操作构成一个群。[2]

动作序列与群元素

把右面连续转四次,所有贴纸都会归位,因此

R4=e,R−1=R3.

R R R R 与空动作的写法、长度都不同,但代表同一个群元素。魔方群的元素可以理解为“一个确定的最终置换”,动作串则是描述它的一种方式。寻找短解,就是在许多等效动作串中寻找较短的表达。

给 48 张非中心贴纸分别编号,任何合法操作都对应一个置换,而且不同操作可由这些编号的最终位置区分。因此 G 可以看作 S48 的一个子群。它只占全部贴纸置换中的很小一部分,因为小块绑定和机械结构限制了允许的变化。

复合操作的逆元

先做 A ,再做 B ,撤销时应先撤销最后做的 B ,再撤销 A 。于是

(AB)−1=B−1A−1.

例如 R U F2 的逆序是 F2 U' R'。将两串接起来,最中间的 F2 F2 先抵消,随后 U U' 和 R R' 依次抵消。

记录完整打乱过程,就能这样复原。但面对一个来历未知的状态,我们通常并不知道当初的动作串。可逆性保证存在撤销操作,并没有直接告诉我们如何找到它。

操作的交换性

右层与左层互不重叠,所以 RL=LR 。相邻的右层与上层则共享小块,先转右面会改变随后上面转动所涉及的对象,因此 RU≠UR 。

两个操作是否相等可以严格检查:只要找到一张贴纸在两种顺序下到达不同位置,就足以证明两个置换不同。这里比较的是整个置换,不是某个恰巧颜色相同的局部画面。

四、面转动的置换表示与圆环模型

贴纸编号与面转动的循环分解

从每个面的外侧正视它,按行把九个位置编号为 1 到 9,中心为 5。U1 表示上面的左上角位置;复原起点上位于该格的贴纸,也命名为“原始 U1 贴纸”。转动以后,两者可能不再重合。

采用六面展开图的连续朝向:前面向上接 U、向下接 D、向右接 R、向左接 L,B 接在 R 的右边。这样下面的编号和动画保持一致。[6]

一次 U 转动产生五个互不相交的 4-循环:

U=(U1 U3 U9 U7)(U2 U6 U8 U4)(R1 F1 L1 B1)(R2 F2 L2 B2)(R3 F3 L3 B3).

前两个循环在上面内部:四张角贴纸循环,四张棱贴纸循环。后三个循环连接四个侧面的顶行,共移动 12 张贴纸。于是一次外层四分之一转总共改变 8+12=20 张编号贴纸的位置,其余 34 张不动。

注意,这里的“角贴纸”是角块上的一个可见面。一个角块的三张贴纸会分别出现在不同的贴纸循环中;这与它们仍属于同一个小块并不矛盾。

九环模型的构造

以右、上、前分别为 x,y,z 轴正方向。每个方向都有三层,坐标可记成 −1,0,1 。固定一个层,只观察绕该轴在四个侧面间流动的贴纸:四面各有三张,总共 12 张。将这条侧带画成闭合曲线,就得到一条环。

三个轴各有三层,因此共有九条环。把同一轴的三条环画成同心圆,便得到截图那种三组圆环的结构。

一张前面贴纸的法向沿 z 轴。它既位于某条固定 x 的侧带,也位于某条固定 y 的侧带,所以在图中属于两条环。每条环有 12 个位置,每个位置被算了两次,于是

9×122=54.

另一种算法是数交点:三组环之间有三种组配对,每种配对包含 3×3 对圆,每对相交两次,因此也是 3×9×2=54 。这里选择的圆半径与排布避免了多个交点重合。

侧带转动的模运算表示

沿某条环,把 12 个位置暂记为 0,1,…,11 。四分之一转将一个面的三格条带送到下一个面,对应

j↦j+3(mod12).

因此这一步分成三个 4-循环:

(0 3 6 9)(1 4 7 10)(2 5 8 11).

反向转动把加 3 改成减 3。重复四次后各点归位,这与原魔方一致。若让所有点只沿环前进一格,得到的将是一个 12-循环,不对应这里的合法转面。

面内贴纸的同步置换

上面的圆环只画出了侧带。转 U 时,上面自身的八张非中心贴纸也要换位。它们发生在 U 面对应的九点簇内,不能只盯着大圆环的滑动而忽略它们。

在下面的动画中选择 U,慢速单步观察:大环上有 12 点移动,面簇内部另有 8 点移动。跟踪编号可以看到,即使同色面看起来没有改变,贴纸仍可能已经换位。

同一次转动:三维魔方与贴纸圆环

圆环模型的对应关系与限制

圆环排布为 54 个位置重新选择了平面坐标,却保留每个合法动作的起点、终点对应关系。只要每个位置都能唯一找回,重新排布就不会丢失完整的贴纸状态。

但曲线相交并不意味着贴纸可以自由换轨。一次合法动作会同步更新整层,不能只挑一个圆点移动。图中的线段首先表示绘图关系,不是允许一颗珠子独自通过的道路。

圆的半径、屏幕上的距离和动画速度,也不属于群的结构。面簇内部使用便于观察的曲线连接正确的端点;不同的连续轨迹可以表示相同的离散置换。判断模型是否正确,要检查每一步完成后的全部贴纸对应关系。

五、交换子、共轭与局部操作

交换子的定义与作用

定义交换子

[A,B]=ABA−1B−1.

仍按从左到右执行。它与完整撤销 AB 的序列 ABB−1A−1 相差一个顺序。如果 A,B 可交换,就能调整顺序并全部抵消,得到 [A,B]=e ;反过来,交换子等于 e 也能推出两者可交换。

因此 [R,L] 最终不改变任何贴纸,而 [R,U] 会留下变化。设计魔方公式时,人们会选取大部分影响可以互相抵消的操作,使剩余变化集中在较少的小块上。交换子提供了构造局部效果的方法,但任意一个交换子并不都“只动三个块”。[7]

循环分解与交换子的阶

令 C=RUR−1U−1 。按前面的贴纸编号计算,它包含两个 6-循环、两个 3-循环,其余贴纸固定。因此

ord(C)=lcm(6,6,3,3)=6,C6=e.

这里的最小公倍数保证四个循环同时归位。只看块的位置,可能会发现有些角块经过两次就回到了原来的角,却仍朝向错误。完整贴纸置换同时记录位置和方向,因此能给出正确周期。

用编号贴纸验证还有一个好处:同颜色的两张贴纸在画面上很像,但编号不会把一次真实换位误认成“没有变化”。

共轭与作用位置的变换

假设 A 是一个已经掌握的局部操作, P 是准备步骤,那么

PAP−1

表示先用 P 把目标对象送入 A 的作用区,执行 A ,最后撤销准备步骤。没有被 A 影响的对象恢复原状,被影响的对象则留下局部变化。这称为共轭。

共轭保留置换的循环长度和阶。可以把它理解为:原来沿某一组编号进行的循环,被一致地搬到了另一组编号上,循环的内部结构没有改变。准备步骤仍须是合法操作,且要留意块的方向,不能任意指定几张独立贴纸来“搬运”。

下面先比较 RU 与 UR,再切换交换子。最后观察 F[R,U]F':它的作用位置改变了,但循环类型仍与 [R,U] 一致。

操作顺序、交换子与共轭

这也解释了魔方公式中的一种常见结构:先把需要处理的块放到熟悉的位置,执行局部公式,再恢复准备动作。理解结构后,公式可以被检查和组合,不必把它当成一串互不相关的转动。

六、状态不变量与可达性

状态坐标与不变量

不变量是无论做多少次合法操作都保持不变的量。寻找不变量时,可以先检查基本生成动作:如果它们全部保持某个量,那么任意有限次组合也保持它。

固定六个中心后,把状态记录为角块排列 πc 、角块方向 ti 、棱块排列 πe 、棱块方向 fi 。角块方向有三种,以 0,1,2 表示;棱块方向有两种,以 0,1 表示。这里的方向标签必须在所有位置采用一致约定,不能随意从观察者的左右判断。[4]

角位置的三个槽按相同手性编号,让 U/D 槽为 0。例如右上前角按 U、R、F 依次记 0、1、2;右下前角则按 D、F、R。白/黄贴纸落入哪个槽,就是方向值。棱位置的第一槽优先取 U/D;没有 U/D 时取 F/B。棱块的参考颜色也按这一优先级选取:它落在第一槽记 0,另一槽记 1。下面的约束使用这套约定。

角块方向约束

所有合法状态都满足

∑i=18ti≡0(mod3).

上、下面的转动只会重新排列方向值,其他面的四分之一转对四个相关角块增加两个 1 和两个 2,总增量为 6≡0(mod3) 。方向和因而保持不变。

单独把一个角拧 120∘ ,会让总和变成 1 或 2,无法通过合法转面回到复原时的 0。两个角分别扭转相反方向则不违反这项约束。

棱块方向约束

棱块满足

∑i=112fi≡0(mod2).

在一致的常用方向约定下,一个生成动作会改变零个或四个棱块的方向值,总变化为偶数。因此只翻转一条棱、其他块完全不变的状态不可达。这里说的是方向坐标,不能把它简单等同于“白色有没有朝上”。

角块与棱块的排列奇偶性

一个外层四分之一转,在块的位置层面同时产生一个角块 4-循环和一个棱块 4-循环。两者各自是奇排列,所以每次转动会同时改变二者的奇偶性。从复原状态出发,它们始终保持一致:

sgn(πc)=sgn(πe).

单独交换两条棱或两个角都会违反条件。注意这说的是块的排列:同一个转动在贴纸层包含五个 4-循环,不能把两种对象的奇偶性混为一谈。[2]

合法状态的计数

角块有 8! 种排列,前七个方向任意选,第八个由模 3 和确定,故有 37 种方向组合。棱块同理,有 12! 种排列和 211 种方向组合。两类排列须同奇偶,再将组合数除以 2:

|G|=8!12!372112=43252003274489856000.

这个等式还使用了一个事实:对正确的小块集合,上述三个条件不仅必要,而且充分。充分性需要能成对纠正方向、用三循环处理偶排列的构造;若两类排列同为奇,先做一次四分之一转使它们同时变偶。配合适当共轭,可把局部构件用于不同位置。仅仅写出计数乘积,并不能替代这个可达性论证。[3]

这里已经固定中心参照系,不再除以整体朝向的 24 种选择。也不能把“每种颜色各九张”当作充分条件:任意乱贴的布局还可能含有根本不存在的颜色对或角块组合。

七、凯莱图与最短路径搜索

贴纸图与状态图

一个图由顶点和连接顶点的边构成。沿边依次经过顶点得到路径;若每条边代价为 1,最短路径就是边数最少的路径。

对魔方可以建立不同的图。圆环图中的点是贴纸位置,一个画面共同描述整颗魔方。用于求解的状态图中,一个点则是完整的合法魔方状态,一条边表示执行一次允许动作。后者一个节点就包含了前者整幅图的信息。

以群元素 g∈G 为顶点,对每个允许动作 s 连接 g 与 gs ,得到群的凯莱图。以复原状态对应单位元 e ,求解就是寻找

gs1s2⋯sk=e

的路径。动作串表示 g−1 ,最短解是在指定步数度量下的最短表达。单张贴纸各自的最短路线不能直接合起来,因为整层动作与小块绑定要求所有对象协调运动。

十六状态子群的凯莱图

暂时只允许 U 和 D 转动。它们可交换,并且各转四次归位,因此每个可达状态都能写成

UaDb,a,b∈{0,1,2,3}.

两个指数分别记录上层和下层的变化,不同指数对产生不同状态。这个子群有 4×4=16 个元素,记作

H=⟨U,D⟩≅C4×C4.

符号 × 在这里把两套独立旋转组成有序对,运算分别对两个坐标模 4 相加; ≅ 表示两种描述的操作结构相同。

在下面的图中,节点 (a,b) 代表整颗 UaDb 魔方。选择节点,可以直接查看其实际状态。它是完整魔方问题中的一个受限子问题,不代表任意打乱都能用 U、D 复原。

16 个魔方状态中的 BFS 与最短解

广度优先搜索与最短路径

广度优先搜索(BFS)使用先进先出的队列。先访问起点,再访问一步能到达的状态,再访问两步能到达的新状态,依次向外扩展。每次发现新节点时,记录从哪个父节点、通过哪个动作到达它。

因为每条边的代价都为 1,首次发现目标时,所有可能更短的层都已被处理。沿父指针从目标回溯到起点,再倒转记录顺序,就得到一条最短解。

访问集合用来避免重复。U D 与 D U 是不同动作串,却通往同一节点;四次 U 又回到起点。如果把每条动作串都当成新状态,搜索会重复劳动。动画实际计算邻居和父指针,然后按层展示结果。

转动度量与状态图直径

QTM 是四分之一转度量,一次 90∘ 算一步,半转算两步。HTM 是半转度量,一次 90∘ 或 180∘ 都算一步。起点 (2,2) 在 QTM 中需要四步,在 HTM 中用 U2 D2 两步即可复原。

对于完整三阶魔方,已证明的最远最短距离分别为 QTM 的 26 和 HTM 的 20。这叫状态图的直径;凯莱图各节点具有相同的局部结构,最远的两点距离也等于从复原节点出发的最大距离。[8][9]

“所有状态都能在 20 步内复原”不表示每个状态都需要 20 步,也不保证随便一种算法都会给出这样的解。记录打乱后倒放,只展示一个解,没有排除更短的路径。

完整图约有 4.3×1019 个节点,无法像这个小实验一样直接展开。实际求解器使用启发式下界、预计算和子群来减少搜索。两阶段算法先把状态送入方向受限的子群,再在其中复原;这样的结构化搜索能快速得到短解,但“使用两阶段”本身不等于保证全局最短。[10]

置换、群与图的统一视角

圆环图使同一组贴纸置换更容易被追踪。群论解释这些操作如何组合、撤销,以及哪些状态可以到达;状态图进一步把复原写成一条路径。理解时始终记住两件事:圆点到底代表贴纸还是完整状态,以及一次合法操作必须让哪些对象同时移动。

参考资料

  1. 灵感截图:The Math Flow 发布的圆环动画。原始制作作者未核实,此处保留的是阅读时看到的截图。
  2. Michael Hutchings — The mathematics of Rubik’s Cube。群、置换、魔方操作与不变量;幻灯片第 8–9、23、28–34 页。
  3. Jaap Scherphuis — Group Theory for puzzles。排列奇偶性、三循环、共轭与交换子;第 5、7 节。
  4. Herbert Kociemba — The Cubie Level。角块、棱块的位置与方向表示。
  5. WCA Regulations — Article 12: Notation。六面转动、逆转和半转记号。
  6. Herbert Kociemba — The Faceletlevel。贴纸层编号与位置表示。
  7. Jaap Scherphuis — Useful Mathematics。Conjugation、Commutation 两节。
  8. God's Number is 20。2010 年完整三阶魔方 HTM 直径的计算证明。
  9. God's Number is 26 in the Quarter Turn Metric。2014 年 QTM 直径的计算证明。
  10. Herbert Kociemba — The Two-Phase Algorithm Coordinates。两阶段求解及子群坐标。