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

一、群论基础
集合、映射与置换
集合是一组对象。例如,
如果不同输入不会送到同一个输出,并且每个输出都有输入与之对应,这个映射就是双射。对有限集合而言,双射把所有对象重新安排一遍,既没有重复,也没有遗漏。一个集合到自身的双射称为置换。把四张有编号的卡片重新排列,就是一个例子。
为什么强调双射?因为每个输出都能唯一地追溯到原来的输入。于是这个操作可以撤销。将卡片合并、丢弃或复制,都失去了这种可逆性。
操作的复合
“运算”不只指数字的加法或乘法。先做一个动作
后文省略乘号,写
相同的整体效果视为同一个操作。转一整圈与完全不转,对正方形四个顶点的最终位置没有区别;群论在这里比较最终作用,而不记录手走过的轨迹。
群的定义与公理
设
封闭性:做完集合中的两个操作,得到的整体操作仍属于这个集合。
结合律:连续做三件事,可以先把前两件看作整体,也可以先把后两件看作整体。
这里没有交换动作的先后,只改变了分组方式。
单位元:存在一个“不改变结果”的操作
逆元:每个操作
有些教材把封闭性包含在“二元运算”的定义中,因此只另列三条公理,内容相同。群的定义不要求交换律
正方形旋转与循环群
给正方形的四个顶点贴上 A、B、C、D。只允许绕中心旋转整数个
指数表示重复次数,
“模 4”就是除以 4 后保留余数,例如
试着正转四次,或者正转一次再逆转一次。比较顶点标记,而不只看正方形的外轮廓。
置换的循环分解
循环
一个置换可能包含多个互不相交的循环。例如
任何有限置换都可以这样分解。方法是从一个编号出发,反复追踪它被送到哪里,直到回到起点;再从一个尚未访问的编号开始。没有移动的编号是长度为 1 的循环,通常省略。
群的基本概念与排列奇偶性
群的阶
能通过反复组合及取逆产生全部操作的一组元素,称为生成元。记号
最后介绍一个判断排列是否合法的工具。只交换两个对象称为对换。任何置换都能分解成对换;虽然分解方式不唯一,对换次数的奇偶性却保持一致,因此可以区分偶排列与奇排列。用符号
长度为
例如 4-循环是奇排列,3-循环是偶排列;两个奇排列组合后是偶排列。后面魔方的一个重要限制就来自这条规则。
二、三阶魔方的结构与表示
小块、贴纸与状态
三阶魔方的外观是每面
| 小块 | 个数 | 每块的贴纸数 | 需要追踪的信息 |
|---|---|---|---|
| 中心块 | 6 | 1 | 给六个面提供参考颜色 |
| 棱块 | 12 | 2 | 位置和翻转方向 |
| 角块 | 8 | 3 | 位置和扭转方向 |
因此贴纸总数为
贴纸是可以被跟踪的对象,贴纸位置是某一面上的固定格子。白色贴纸可以从上面移到前面,但“上面左上角”这个位置的定义不变。整个状态则必须记录所有小块的位置及方向,不能只描述某一张贴纸。
小块的位置与方向
棱块占据一个位置时有两种方向。比如白红棱块即使回到了白、红两中心之间,也可能把白色朝向红面、红色朝向白面,这叫翻转。
角块在一个角位置有三种方向。白红绿角块可以绕自身的角方向扭转
因此复原需要同时满足两件事:块的位置正确,块的方向也正确。本文讨论常见的纯色三阶魔方,不计中心贴纸上的箭头、文字或图案是否转正。
参照系与转动记号
固定一套观察方向:上白、下黄、前绿、后蓝、右红、左橙。相对面分别是白/黄、绿/蓝、红/橙。中心块给出这套坐标,在本文的模型中保持固定。
| 面 | 上 | 下 | 右 | 左 | 前 | 后 |
|---|---|---|---|---|---|---|
| 记号 | U | D | R | L | F | B |
单独一个字母表示该面顺时针转
2 表示转
R' 是右面逆转,U2 是上面半转。顺时针必须从所转面的外侧、正对那个面判断,背面和底面也遵守同一规则。[5]
转一个外层,会同时带动四个角块、四个棱块,以及该面的中心朝向;纯色中心本身的位置不变。本文只开放这六个外层的转动。整体拿起魔方换方向属于改变观察坐标,暂不作为新的打乱状态。
三、魔方群与操作复合
把六种基本面转动、它们的逆操作,以及任意有限次组合得到的操作放在一起,定义
封闭性在定义中已经包含:两串合法转动接起来,仍是一串合法转动。结合律来自操作复合,三串动作的分组不影响实际执行顺序。空动作是单位元
动作序列与群元素
把右面连续转四次,所有贴纸都会归位,因此
R R R R 与空动作的写法、长度都不同,但代表同一个群元素。魔方群的元素可以理解为“一个确定的最终置换”,动作串则是描述它的一种方式。寻找短解,就是在许多等效动作串中寻找较短的表达。
给 48 张非中心贴纸分别编号,任何合法操作都对应一个置换,而且不同操作可由这些编号的最终位置区分。因此
复合操作的逆元
先做
例如 R U F2 的逆序是 F2 U' R'。将两串接起来,最中间的 F2 F2 先抵消,随后 U U' 和 R R' 依次抵消。
记录完整打乱过程,就能这样复原。但面对一个来历未知的状态,我们通常并不知道当初的动作串。可逆性保证存在撤销操作,并没有直接告诉我们如何找到它。
操作的交换性
右层与左层互不重叠,所以
两个操作是否相等可以严格检查:只要找到一张贴纸在两种顺序下到达不同位置,就足以证明两个置换不同。这里比较的是整个置换,不是某个恰巧颜色相同的局部画面。
四、面转动的置换表示与圆环模型
贴纸编号与面转动的循环分解
从每个面的外侧正视它,按行把九个位置编号为 1 到 9,中心为 5。U1 表示上面的左上角位置;复原起点上位于该格的贴纸,也命名为“原始 U1 贴纸”。转动以后,两者可能不再重合。
采用六面展开图的连续朝向:前面向上接 U、向下接 D、向右接 R、向左接 L,B 接在 R 的右边。这样下面的编号和动画保持一致。[6]
一次 U 转动产生五个互不相交的 4-循环:
前两个循环在上面内部:四张角贴纸循环,四张棱贴纸循环。后三个循环连接四个侧面的顶行,共移动 12 张贴纸。于是一次外层四分之一转总共改变
注意,这里的“角贴纸”是角块上的一个可见面。一个角块的三张贴纸会分别出现在不同的贴纸循环中;这与它们仍属于同一个小块并不矛盾。
九环模型的构造
以右、上、前分别为
三个轴各有三层,因此共有九条环。把同一轴的三条环画成同心圆,便得到截图那种三组圆环的结构。
一张前面贴纸的法向沿
另一种算法是数交点:三组环之间有三种组配对,每种配对包含
侧带转动的模运算表示
沿某条环,把 12 个位置暂记为
因此这一步分成三个 4-循环:
反向转动把加 3 改成减 3。重复四次后各点归位,这与原魔方一致。若让所有点只沿环前进一格,得到的将是一个 12-循环,不对应这里的合法转面。
面内贴纸的同步置换
上面的圆环只画出了侧带。转 U 时,上面自身的八张非中心贴纸也要换位。它们发生在 U 面对应的九点簇内,不能只盯着大圆环的滑动而忽略它们。
在下面的动画中选择 U,慢速单步观察:大环上有 12 点移动,面簇内部另有 8 点移动。跟踪编号可以看到,即使同色面看起来没有改变,贴纸仍可能已经换位。
圆环模型的对应关系与限制
圆环排布为 54 个位置重新选择了平面坐标,却保留每个合法动作的起点、终点对应关系。只要每个位置都能唯一找回,重新排布就不会丢失完整的贴纸状态。
但曲线相交并不意味着贴纸可以自由换轨。一次合法动作会同步更新整层,不能只挑一个圆点移动。图中的线段首先表示绘图关系,不是允许一颗珠子独自通过的道路。
圆的半径、屏幕上的距离和动画速度,也不属于群的结构。面簇内部使用便于观察的曲线连接正确的端点;不同的连续轨迹可以表示相同的离散置换。判断模型是否正确,要检查每一步完成后的全部贴纸对应关系。
五、交换子、共轭与局部操作
交换子的定义与作用
定义交换子
仍按从左到右执行。它与完整撤销
因此 [R,L] 最终不改变任何贴纸,而 [R,U] 会留下变化。设计魔方公式时,人们会选取大部分影响可以互相抵消的操作,使剩余变化集中在较少的小块上。交换子提供了构造局部效果的方法,但任意一个交换子并不都“只动三个块”。[7]
循环分解与交换子的阶
令
这里的最小公倍数保证四个循环同时归位。只看块的位置,可能会发现有些角块经过两次就回到了原来的角,却仍朝向错误。完整贴纸置换同时记录位置和方向,因此能给出正确周期。
用编号贴纸验证还有一个好处:同颜色的两张贴纸在画面上很像,但编号不会把一次真实换位误认成“没有变化”。
共轭与作用位置的变换
假设
表示先用
共轭保留置换的循环长度和阶。可以把它理解为:原来沿某一组编号进行的循环,被一致地搬到了另一组编号上,循环的内部结构没有改变。准备步骤仍须是合法操作,且要留意块的方向,不能任意指定几张独立贴纸来“搬运”。
下面先比较 RU 与 UR,再切换交换子。最后观察 F[R,U]F':它的作用位置改变了,但循环类型仍与 [R,U] 一致。
这也解释了魔方公式中的一种常见结构:先把需要处理的块放到熟悉的位置,执行局部公式,再恢复准备动作。理解结构后,公式可以被检查和组合,不必把它当成一串互不相关的转动。
六、状态不变量与可达性
状态坐标与不变量
不变量是无论做多少次合法操作都保持不变的量。寻找不变量时,可以先检查基本生成动作:如果它们全部保持某个量,那么任意有限次组合也保持它。
固定六个中心后,把状态记录为角块排列
角位置的三个槽按相同手性编号,让 U/D 槽为 0。例如右上前角按 U、R、F 依次记 0、1、2;右下前角则按 D、F、R。白/黄贴纸落入哪个槽,就是方向值。棱位置的第一槽优先取 U/D;没有 U/D 时取 F/B。棱块的参考颜色也按这一优先级选取:它落在第一槽记 0,另一槽记 1。下面的约束使用这套约定。
角块方向约束
所有合法状态都满足
上、下面的转动只会重新排列方向值,其他面的四分之一转对四个相关角块增加两个 1 和两个 2,总增量为
单独把一个角拧
棱块方向约束
棱块满足
在一致的常用方向约定下,一个生成动作会改变零个或四个棱块的方向值,总变化为偶数。因此只翻转一条棱、其他块完全不变的状态不可达。这里说的是方向坐标,不能把它简单等同于“白色有没有朝上”。
角块与棱块的排列奇偶性
一个外层四分之一转,在块的位置层面同时产生一个角块 4-循环和一个棱块 4-循环。两者各自是奇排列,所以每次转动会同时改变二者的奇偶性。从复原状态出发,它们始终保持一致:
单独交换两条棱或两个角都会违反条件。注意这说的是块的排列:同一个转动在贴纸层包含五个 4-循环,不能把两种对象的奇偶性混为一谈。[2]
合法状态的计数
角块有
这个等式还使用了一个事实:对正确的小块集合,上述三个条件不仅必要,而且充分。充分性需要能成对纠正方向、用三循环处理偶排列的构造;若两类排列同为奇,先做一次四分之一转使它们同时变偶。配合适当共轭,可把局部构件用于不同位置。仅仅写出计数乘积,并不能替代这个可达性论证。[3]
这里已经固定中心参照系,不再除以整体朝向的 24 种选择。也不能把“每种颜色各九张”当作充分条件:任意乱贴的布局还可能含有根本不存在的颜色对或角块组合。
七、凯莱图与最短路径搜索
贴纸图与状态图
一个图由顶点和连接顶点的边构成。沿边依次经过顶点得到路径;若每条边代价为 1,最短路径就是边数最少的路径。
对魔方可以建立不同的图。圆环图中的点是贴纸位置,一个画面共同描述整颗魔方。用于求解的状态图中,一个点则是完整的合法魔方状态,一条边表示执行一次允许动作。后者一个节点就包含了前者整幅图的信息。
以群元素
的路径。动作串表示
十六状态子群的凯莱图
暂时只允许 U 和 D 转动。它们可交换,并且各转四次归位,因此每个可达状态都能写成
两个指数分别记录上层和下层的变化,不同指数对产生不同状态。这个子群有
符号
在下面的图中,节点
广度优先搜索与最短路径
广度优先搜索(BFS)使用先进先出的队列。先访问起点,再访问一步能到达的状态,再访问两步能到达的新状态,依次向外扩展。每次发现新节点时,记录从哪个父节点、通过哪个动作到达它。
因为每条边的代价都为 1,首次发现目标时,所有可能更短的层都已被处理。沿父指针从目标回溯到起点,再倒转记录顺序,就得到一条最短解。
访问集合用来避免重复。U D 与 D U 是不同动作串,却通往同一节点;四次 U 又回到起点。如果把每条动作串都当成新状态,搜索会重复劳动。动画实际计算邻居和父指针,然后按层展示结果。
转动度量与状态图直径
QTM 是四分之一转度量,一次
U2 D2 两步即可复原。
对于完整三阶魔方,已证明的最远最短距离分别为 QTM 的 26 和 HTM 的 20。这叫状态图的直径;凯莱图各节点具有相同的局部结构,最远的两点距离也等于从复原节点出发的最大距离。[8][9]
“所有状态都能在 20 步内复原”不表示每个状态都需要 20 步,也不保证随便一种算法都会给出这样的解。记录打乱后倒放,只展示一个解,没有排除更短的路径。
完整图约有
置换、群与图的统一视角
圆环图使同一组贴纸置换更容易被追踪。群论解释这些操作如何组合、撤销,以及哪些状态可以到达;状态图进一步把复原写成一条路径。理解时始终记住两件事:圆点到底代表贴纸还是完整状态,以及一次合法操作必须让哪些对象同时移动。
参考资料
- 灵感截图:The Math Flow 发布的圆环动画。原始制作作者未核实,此处保留的是阅读时看到的截图。
- Michael Hutchings — The mathematics of Rubik’s Cube。群、置换、魔方操作与不变量;幻灯片第 8–9、23、28–34 页。
- Jaap Scherphuis — Group Theory for puzzles。排列奇偶性、三循环、共轭与交换子;第 5、7 节。
- Herbert Kociemba — The Cubie Level。角块、棱块的位置与方向表示。
- WCA Regulations — Article 12: Notation。六面转动、逆转和半转记号。
- Herbert Kociemba — The Faceletlevel。贴纸层编号与位置表示。
- Jaap Scherphuis — Useful Mathematics。Conjugation、Commutation 两节。
- God's Number is 20。2010 年完整三阶魔方 HTM 直径的计算证明。
- God's Number is 26 in the Quarter Turn Metric。2014 年 QTM 直径的计算证明。
- Herbert Kociemba — The Two-Phase Algorithm Coordinates。两阶段求解及子群坐标。