解密魔方 · 你手上的那个群

timeobserver137 番外 · 实践篇。不看前面八集也能读。 正文只讲故事和概念脉络,推导在附录 A–G(有一处只给方向、没有走完,附录 C 末尾写明了);附录里标「本文实算」的每一个数都可以自己复算,历史上的数字出处见文末。 看过前面几集的:第二、三集讲过的陪集、拉格朗日定理和商群,会在第二、五、六、八节再出现。


配套视频(YouTube)

0. 一个还原不了的魔方

这个魔方,看上去差一步就可以还原了,除了角上的那一个颜色不对以外,其他的颜色和面都已经完成。

但是事实上随便我们怎么拧,拧一个下午回不去,拧一辈子也回不去。

这不是因为它难,而是它根本就不在「拧得出来」的那些状态里。这个与我们之前讨论的群论的奇偶性有一定的关系,在这个番外集中,我们就一起来看看魔方的魅力和秘密。

1. 一九七四年,布达佩斯的一个木盒子

鲁比克(Ernő Rubik)一九四四年生在布达佩斯,先学建筑,后来又读了室内设计。七十年代他在布达佩斯的应用艺术学院教设计课,业余做各种几何模型。一九七四年,他用二十七个小木块拼出了第一个能转、又不会散架的立体。他自己后来说,造这东西的时候,并不是要做一道谜题;可是把它拧乱之后,他花了一个多月才第一次把它拧回去。

一九七五年一月,他提交了匈牙利专利申请,专利上的名字是「空间逻辑玩具」。一九七七年底,这个东西在匈牙利开始卖,匈牙利语的名字直译过来就是「魔方」;一九七九年授权给美国的 Ideal 玩具公司,改名 Rubik’s Cube,一九八〇年起卖到了全世界。

这篇要讲的事,都从那个木盒子说起。

2. 先把它数出来

观察魔方的构造,它有八个角块、十二个棱块,以及中心永远都不会随着转动改变的那六块。魔方摆出来的每一个样子,叫做一个状态;一共能有多少个不同的样子,叫做状态数。

暂且不考虑如何将魔方还原,把所有的摆法都算进去:角块可以怎么排、每个角可以朝哪个方向,棱块可以怎么排、每个棱翻没翻。八个角块排进八个角位有 8! 种排法,每个角块三格朝向,八个就是 383^8;十二个棱块有 12! 种排法,每个棱两种朝向,是 2122^{12};四个数相乘(附录 B 逐项算了)。乘出来是 519,024,039,293,878,272,000。

而真正靠转动能得到的状态有 43,252,003,274,489,856,000。

前一个数正好是后一个数的十二倍。

这个十二也不是笼统乘上去的修正系数。它其实是 3×2×2,三个各自独立的因子,对应三件在魔方上做不到的事:单独扭一个角,单独翻一个棱,只交换两个块而别的都不动。第零节那个无法还原的魔方犯的正是第一条。

这三件事能用群论说清楚。每一件对应一个量:八个角各自扭了几格加起来除以三的余数、十二个棱翻转的总次数是奇是偶、二十个块两两交换的总次数是奇是偶。转动任何一个面,这三个量都不变(附录 C 逐条验算了六个面),所以不管接多少步,它们都和还原态一样。三个量分别只有 3、2、2 种取值,乘起来就是那个十二。第三集 讲 sgn 的时候用过同一个工具:一个把「两个动作接起来」变成「两个数加起来」的映射,那一集叫它同态;这里是三个这样的映射并排。只要某个魔方的摆法在这三个量上对不上,它就永远无法回到六个面六种颜色的状态。

那我们可能会继续追问,既然知道了永远无法复原的模式,是否存在一套可以将魔方复原的方法呢?如果有,这套方法究竟是什么,又如何与我们的群论相关?接下来我们就从最基本的转动观察,一步步得到还原魔方的公式。

3. 六个动作,生成一切

魔方上能做的事只有六件:转六个面。那些看起来很复杂的还原步骤,也只是把这六件事接起来做。数学上把这六个叫生成元;所有能这样接出来、又都能撤销的动作放在一起,就叫一个群。这篇后面说的「魔方群」,指的就是它。

这一集还会有一张动起来的图:我们将五十四个魔方的色块投影到五十四个点上,按六个面聚成六小片;每一种转动对应一个圆环,把这次会动到的魔方色块串起来。转哪个面,哪个环就亮起来,环上的点顺着环挪过去,像拨一个转盘。

一个点是一个魔方色块,一个环则是一种转动。

4. 一层一层拧回去

先定义一下魔方的几种转动。魔方表面一共有五十四个小方格,这里我们叫它色块(早期的魔方是把彩色纸片贴上去的,所以附录里也叫它贴纸):每个角块带三个色块,每个棱块带两个,每个中心块一个。拿着魔方,面对自己的那一面叫 F(front,前),它的对面叫 B(back,后),上面是 U(up),下面是 D(down),左面 L(left),右面 R(right)。一个字母表示把那一面顺时针转九十度,「顺时针」是正对着那一面看过去的方向;字母后面加一撇(如 R′R')表示逆时针转九十度;加 2(如 R2R2)表示转一百八十度。拿实物核对一下:做一次 RR,前面靠右的那一列会往上走,顶面靠右的那一列会往后走。一串字母就是按顺序做下去:R U R′R\,U\,R' 是先转右面,再转上面,再把右面转回来。附录 A 把一次 RR 之后每个色块的去向都列了出来。

一个位置用它所在的面来叫:UFR 是上、前、右三面交汇的那个角,UF 是上面和前面之间的那条棱。

入门的还原方法都是一层一层来的:白色面朝下,黄色面朝上。官方说明书分八步,这里照它的分法和顺序。每一步只管一件事;从第三步起,每一步做完,前面拼好的部分都还在原处(第一步的花是个例外:它只是把四条白棱先集中到顶层,第二步会把它们一瓣一瓣翻下去)。下面按顺序说,每一步说它做什么,有公式的给出公式和它到底动哪几块(本文实算),以及在后面那个例子里用了几步。

想对照着拧,可以看官方的 Rubik’s 3×3 Solve Guide,或者 Ruwix 的 入门法逐步图解;视频里这一节从 4:50 开始。每一步后面附一段动图,取自视频里的那个例子:随机打乱二十五步,再按这八步拧回去(就是本节末尾「真实还原一个」里那一个)。动图左上角是第几步和正在做的公式,下方是这一步拧了几下、一共几下;左边两个魔方是同一个魔方的前后两面,右边是第三节那个转盘图。

第一步,拼一朵花。 把四条带白色的棱找出来,转到顶层,白色朝上,围着黄色中心,像一朵四瓣的花。这一步不用公式,看着拧就行。例子里用了 7 步。

动图:例子里的第一步,拼花,7 下。

第二步,白十字。 转 U,把一片花瓣转到和它侧面颜色相同的那一面,再把那一面转一百八十度,花瓣就翻到了底面,白色朝下。四瓣翻完,底面是一个白十字,每条棱的侧面颜色都和中心对上。例子里 8 步。

动图:例子里的第二步,白十字,8 下。

第三步,白角。 把一个白角转到它要去的格子的正上方,拿着魔方让这个角在右前方。白色朝右时重复做

R U R′ U′R\,U\,R'\,U'

直到它落进去(官方网页版把它的前三步 R U R′R\,U\,R' 叫「右扳机」:转右面、转顶层、右面转回;小册子这一步用的是白十字朝上、带 DD 的另一组公式,见来源 15);白色朝前也一样,接着重复做,一共五遍(也可以换个方向拿,让这个角到左前方、白色朝左,用左手做一遍镜像 L′ U′ L UL'\,U'\,L\,U,结果相同;下面的例子用的是五遍);白色朝上,一共三遍:先做两遍 R U R′ U′R\,U\,R'\,U',它就翻成白色朝右,再做一遍;角已经在底层但位置或朝向不对,先用同一条公式把它顶上来。这条公式只动顶层的三个角和两条棱、一条中层棱,以及正要填的那一个底层格子;白十字和已经放好的角都不碰。例子里 41 步。

动图:例子里的第三步,白角,41 下(R U R′ U′R\,U\,R'\,U' 做了三遍、两遍、五遍)。

第四步,中层。 第一面在下面,中层还有四条棱没归位,它们都在顶层(如果有一条卡在中层的错误位置、或位置对了但翻了面,先用下面的公式往那个格子里放别的棱,它就被顶出来了)。转 U,让一条不带黄色的棱的侧面颜色和中心对齐,拿着魔方让这一面朝自己,再看它顶上那个颜色是左边还是右边那一面的。要去右边的格子,用

U R U′ R′  U′ F′ U FU\,R\,U'\,R'\;U'\,F'\,U\,F

要去左边的格子,用

U′ L′ U L  U F U′ F′U'\,L'\,U\,L\;U\,F\,U'\,F'

这两条公式只动顶层(三个角、四条棱)和正要填的那一条中层棱。例子里 31 步。

动图:例子里的第四步,中层,31 下。

第五步,黄十字。 现在只剩顶层。先让顶层四条棱黄色朝上,用

F  U R U′ R′  F′F\;U\,R\,U'\,R'\;F'

做之前先看顶面的黄色是什么样(只看中心和四条棱,角上的黄色不算),按说明书的三张图持握:只有中心是黄的(一个点);中间一横排三个黄(一条线,横着放);黄色在中心、后中、左中(一个拐角,开口朝前右)。做完若还不是十字,重新对图再做,最多三遍。它只动顶层的四个角和三条棱。例子里 6 步。

动图:例子里的第五步,黄十字,6 下。

第六步,黄面。 把四个角扭到黄色朝上,公式是

R U R′ U R U2 R′R\,U\,R'\,U\,R\,U2\,R'

持法看顶面有几个角已经黄色朝上:一个都没有,就转顶层,让左前那个角的黄色色块朝左面(说明书的口诀「none, left」);有一个,把它放在左前方(口诀「喂鱼」:那个黄角像鱼头,从你左手吃东西);有两个,转到能把左手拇指按在前面左上角那个黄色色块上的位置。做完若没全黄,重新对图再做,可能要做好几遍,而且不是按固定顺序过渡。它只动顶层(四个角、三条棱)。例子里做了两遍,14 步。

动图:例子里的第六步,黄面,公式做了两遍,14 下。

第七步,黄角摆位。 四个角都朝上了,再把它们换到正确的位置。先转 U,看能不能让两个角同时到位(它们侧面的颜色都和中心对上);能就把这两个角放到后面(说明书叫它们「尾灯」:对的角像车尾灯,放在车尾),做

R′ F R′ B2 R F′ R′ B2 R2  U′R'\,F\,R'\,B2\,R\,F'\,R'\,B2\,R2\;U'

对的两个角相邻,就这样放好做一遍,四个角全到位;对角的两个没法同时放到后面,随便拿着做一遍,再转 U 就能让相邻的两个到位,按相邻的再做一遍。前九步只把三个角轮换一圈,不扭转、不碰棱(本文实算),最后的 U′U' 只是把顶层转回对齐。例子里 11 步。

动图:例子里的第七步,黄角摆位,11 下。

第八步,黄棱摆位。 最后四条棱。把已经整面同色的那个侧面放到后面(没有就随便放),做

F2 U L R′ F2 L′ R U F2F2\,U\,L\,R'\,F2\,L'\,R\,U\,F2

它只把前、左、右三条棱转一圈,后面那条不动,角一块不碰(本文实算)。最多三遍,每一遍之前都重新找整面同色的侧面放到后面(公式不碰后面那条棱,所以做过一遍之后一定有一面是整的);若前面那条棱的颜色和右面中心相同,把两个 UU 改成 U′U'。例子里 0 步。

动图:例子里的第八步。这一次四条棱已经在原位,一下都不用拧;动图只是把公式读一遍,示意它会让哪三条棱转一圈。

真实还原一个。 从还原态出发,随机拧二十五步把它打乱:

D′ R′ L U′ B2 R D2 U′ B′ F U′ L′ U2 F′ U2 B2 L′ U′ R F′ U′ L U′ F′ U′D'\,R'\,L\,U'\,B2\,R\,D2\,U'\,B'\,F\,U'\,L'\,U2\,F'\,U2\,B2\,L'\,U'\,R\,F'\,U'\,L\,U'\,F'\,U'

然后按上面八步拧回去:拼花 7 步,白十字 8 步,白角 41 步,中层 31 步,黄十字 6 步,黄面 14 步,黄角摆位 11 步,黄棱摆位 0 步,合计 118 步(同一步里相邻的同面转动已合并;只有黄面那一步照公式完整做了两遍,两遍接缝处的转动没有合并;本文实算:打乱加上这 118 步,每一块回到原位、朝向全对)。黄棱那一步是 0 步,是这个打乱的巧合:前七步没有一步管过四条黄棱的位置,做完第七步它们可能的排法有十二种,这次正好是排好的那一种;一般情况下这一步要做一到三遍。八步的完整转动序列在附录 D 末尾,动画按它画:每一步做完,亮出这一步拼好的块。

这些公式是哪里来的。 拆开看,除了拼花和白十字那两步看着拧,公式全是两个动作。一个叫换向器:做 A,做 B,撤销 A,撤销 B,写作 [A,B]=A B A−1 B−1[A,B]=A\,B\,A^{-1}\,B^{-1}。两段各自动一大片,撤销之后一部分块回到原位,留下来的是两段共同范围附近的那几块:[R,U][R,U] 的两段共有三块,动到的十三块里回来六块;附录 D 的算例两段只共有一块,十五块里回来十二块(均为本文实算)。另一个叫共轭:先做一步 XX,把要修的块送到公式够得着的地方,做公式,再把 XX 撤销,写作 X A X−1X\,A\,X^{-1},同一招,换个地方使。第三步的 R U R′ U′R\,U\,R'\,U' 就是 [R,U][R,U];中层往右放的公式是两个换向器接起来([U,R][U,R] 接 [U′,F′][U',F']),往左放的是它的镜像。末层四条公式全是「换向器外面套一层共轭」(黄角那条不算最后对齐的 U′):黄十字 F [U,R] F′F\,[U,R]\,F';黄面 R [U R′, U] R′R\,[U\,R',\,U]\,R';黄角摆位的前九步 R′ [F, R′ B2 R] RR'\,[F,\,R'\,B2\,R]\,R;黄棱摆位 (F2 U) [U2, R2 F2 R2] (F2 U)−1(F2\,U)\,[U2,\,R2\,F2\,R2]\,(F2\,U)^{-1},这一条展开是十一步,和说明书印的九步是同一个群元素(四条都是本文实算;用程序穷举过,A、B 都不超过三步时这一条没有纯换向器写法,所以在这个长度内非套一层共轭不可)。第五、六步里先转一下 U 再做公式,是共轭的前一半:把要修的块送到公式够得着的地方;那一下 U 不用撤销,因为这两步只看朝向,顶层转到哪都一样。附录 D 把这两个动作逐块算了一遍。

图 D:七条公式各写一行,换向器的两段和外面的共轭用颜色标出

图 D:换向器是「做 A,做 B,撤销 A,撤销 B」,动到的只有两段共同范围附近的那几块;共轭是「先用 X 把要修的块送到公式够得着的地方,做完再把 X 撤销」。图例:A 绿色,B 橙色,撤销它们的 A′、B′ 与原段同色但淡一级,外面的 X…X′ 用金色框住。

这八步的顺序本身也有讲究:从白十字起,每做完一步,就有一批块被锁定,后面每一步做完,它们都还在原处。第五节讲的就是这件事的数学版本。

5. 把还原写成一条链

一九八一年,英国数学家 Morwen Thistlethwaite 把上一节那种一步锁定一批块的做法推到了底:把还原这件事拆成了四段。他一九七二年在曼彻斯特拿到数学博士,之后三年去学了钢琴,一九七五年才回头以数学为业,做出这个办法的时候在伦敦南岸理工学院教书,后来以纽结理论知名。他的办法是:每做完一段,就有一批块被锁定,同时有几种转动从此不再用,能到的状态随之变少。最后一段结束,只剩还原态。用这个办法他证明了,任何状态五十二步以内都能还原,这是当时最好的上界。

四段分别做什么,按可以画出来的方式列在下面。「还剩的状态数」是把第二节那个总数逐段除出来的,每一步都除尽(本文实算);每段的「情形数」出自来源 13。

段这一段做成什么这一段的情形数做完后还能用的转动做完后还剩的状态数
起点打乱的魔方六个面都可以转九十度43,252,003,274,489,856,000
一把十二条棱的翻转全部摆正2,048 = 2112^{11}L,R,F,BL,R,F,B 随便转;U,DU,D 只转一百八十度21,119,142,223,872,000
二把八个角的扭转全部摆正;把 UF、UB、DF、DB 这四条棱放回左右两面之间的那一圈1,082,565 = 37×4953^{7}\times 495L,RL,R 随便转;其余四面只转一百八十度19,508,428,800
三剩下八条棱各自放回自己那一圈;八个角分成两组,各自回到自己那组的四个位置;把奇偶调成一致29,400 = 70×70×670\times70\times6六个面都只转一百八十度663,552
四只用一百八十度的转动,把剩下的全部归位663,552不再需要转动1

每一段结束时,能做的转动比上一段少,能到的状态也比上一段少:四个范围一个套一个,后一个包在前一个里面。数学上这叫一条子群链。第三集 讲伽罗瓦的时候把 S4S_4 一层层剥开:S4S_4 缩到 A4A_4,再缩到 V4V_4,一路缩到只剩 ee,那一集叫它合成列。形状和这里一模一样;那里一层层剥,是为了看出四次方程为什么解得开、五次的 A5A_5 为什么剥不动,这里一层层剥,是为了把魔方拧回去。还原不必在四千三百亿亿个状态里乱找,可以一层层缩小范围。

这张表就是动画的分镜:每一段亮出这段锁定的块,划掉从此不再用的转动,角落里的状态数跟着缩小,四段之后只剩一个。

今天的计算机解法基本都是这个思路。一九九二年,科先巴(Herbert Kociemba)把四段压成两段,这就是两阶段算法;他后来写的求解程序 Cube Explorer 用的就是它,任何状态通常不到一秒就能给出二十步以内的解法。两阶段的第一站就是上表第二段做完的那个范围(换一个方向摆:上下两面随便转,其余四面只转一百八十度),附录 E 算了它有 19,508,428,800 个状态,整个魔方群被它切成 2,217,093,120 块。这也是下一节那个证明的起点。

6. 二十步

二〇一〇年七月,罗基奇(Tomas Rokicki)、科先巴、Morley Davidson 和 John Dethridge 证明了:任何一个合法的魔方状态,二十步以内都能还原,把一个面转九十度或一百八十度都算一步。这次计算用了大约三十五 CPU-年。一 CPU-年是一个处理器不停地算一年的工作量;按他们自己的换算,一台当时的好台式机要算三十五年,分到 Google 捐出的大批闲置机器上,几个星期就算完了。

四年后,二〇一四年八月,罗基奇和 Davidson 又算出了另一种数法的结果:如果规定一百八十度算两步,那么还原的上限是二十六步。这次计算用了大约二十九 CPU-年,机器在俄亥俄超算中心。

他们的证明并不是把四千三百亿亿个状态逐个算了一遍。他们的思路是把整个状态空间按一个子群切成一块一块(数学上叫陪集),同一块里的状态拧回那个子群用的是同一批转动,所以每一块只要算一次;再用魔方的对称性、并让算过的块顺带覆盖别的块,把要算的块数压到原来的百分之二点五。换句话说,真正让这件事算得完的,是群论。

陪集这个词第二集就出现过:S3S_3 的六个动作,按子群 A3A_3(三个旋转)切成两块,另一块是三个翻转,两块一样大,不重不漏拼满整个群,6=2×36 = 2 \times 3。这就是拉格朗日定理(第三集从头证了一遍)。这里是同一件事放大到四千三百亿亿:子群 HH 有 19,508,428,800 个状态,切出来 2,217,093,120 块,两个数相乘正好是 43,252,003,274,489,856,000,一个不多一个不少(附录 E 算了这道除法)。

第五节那条子群链,和这里的陪集,是同一个想法的两种用法:一个逐段缩小范围,一个逐块给上界。

7. 到多少阶为止

除了最常见的三阶魔方,我们可能还看到过四阶、五阶、甚至十阶魔方,那么在阶数上会不会到了某个阶,就解不开了?就像五次方程没有根式解一样?

答案是不会。任何一个合法的打乱,都是一串转动做出来的。把那串转动倒着做回去,就能回到还原态。还原魔方的这个群是有限的,每个元素都有逆。「能被拧乱」和「能被拧回去」本来就是同一个操作的正反面。

会变的只有步数。n×n×nn\times n\times n 的魔方,最坏情况下需要的还原步数是 Θ(n2/log⁡n)\Theta(n^2/\log n) 这个量级,意思是步数大致按 n2/log⁡nn^2/\log n 的比例增长。这个上界的来历是:把标准解法并行起来,一次转动可以顺手把好几处互不相干的块一起带到位,省下来的正是那个 log⁡n\log n。

所以,问「到多少阶为止」,得到的不是一个阶数,而是一条增长律。真正拦住我们的是造不出来、转不动,不是解不开。

四阶上还有一些有意思的事:第二节那三条守恒量,到了四阶各有各的不同。

角的朝向那一条没变。棱的翻转那一条在四阶没有对应的规则,原因是形状:四阶的棱是成对的两块,单独一块翻不过来。三阶上「翻一个棱」这件事,在四阶表现成把同一条棱的两块对调,那是位置的事,不再是朝向的事。

奇偶那一条最有意思:它没有消失,只是不再看得见了。四阶的中心块会跟着面转一起走,而同色的四块中心长得一模一样,于是角的奇排列可以把痕迹藏进中心里,从表面上看不出哪里不对。三阶每个面只有一个中心,藏不住,痕迹就留在奇偶那一条守恒量上。只要把中心块做成彼此可以区分的(图案魔方就是这样),那个奇排列立刻又变得可见。

玩四阶的人把这类卡住的情形叫 parity,遇上了就得多走一段。它还有另一个来路:三阶的一条棱在四阶是两块,附录 G 的例子就是那一种。它不是四阶「更难」,是三阶那条守恒量在四阶没有了落脚的地方。

三条「做不到」里,翻棱和奇偶这两条是三阶的性质,不是魔方的性质;扭角那一条在四阶照旧成立。

8. 你手上就有一个群

前面我们所讲的八集主要讨论的是单群:不能再往下拆的那种群,像数里的素数。魔方群不是单群,它拆得开。而且拆开它不需要什么深的工具,用第二节的奇偶就够了。

先说什么叫奇偶。八个角块的任何一种排法,都可以通过若干次「两个角互换」得到;互换的次数可以不一样,但它是奇数还是偶数,是定的。转一个面,四个角轮换一圈,相当于三次互换,所以是奇数;连转两次就是偶数。第二节的第三个守恒量说的是,角的奇偶和棱的奇偶乘起来永远是偶;但单看角的那一半,是会变的。

于是魔方群里的操作分成两堆:做完之后角块排成偶排列的,和排成奇排列的。偶的那一堆自成一个群:两个偶操作接起来还是偶的,什么都不做也算偶的,偶操作的逆还是偶的。这一堆占整个魔方群的一半。

它还有一条更强的性质。随便取一个操作 gg,先做 gg,再做偶的那一堆里的某个操作,最后把 gg 撤销。这样「换个地方做」出来的操作,仍然在偶的那一堆里:gg 带来的奇偶和撤销 gg 带来的奇偶互相抵消,中间那一步是偶的,合起来还是偶的。数学上把这样的一堆叫正规子群。这张图第三集画过:S3S_3 的 Cayley 表按 A3A_3 切成两块,一块叫「偶」,一块叫「奇」,偶接偶是偶,偶接奇是奇,奇接奇是偶,整张六乘六的表缩成一张二乘二的表,那一集叫它商群 S3/A3S_3/A_3。魔方群按角的奇偶切开,得到的是同一张二乘二的表:偶的那一堆就是这里的 A3A_3,角排列的符号就是那一集的 sgn。只是这一次,表的一半里有两千一百多亿亿个操作。附录 F 用程序核了一遍:两百个随机操作,角的奇偶乘棱的奇偶全是偶;六十个随机的 gg,换个地方做之后全部还在偶的那一堆里。

一个群只要有一个这样的正规子群(既不是只含「什么都不做」的那一个,也不是它自己),就不是单群。魔方群有,所以它不是单群。附录 F 里另外还有两个:把十二个棱全部翻一遍的那个操作和「什么都不做」组成的两元素子群,以及把每块都放回原位、只改变朝向的那一堆。

前面八集里的单群,拆不动;魔方群拆得开,而且拆法就写在它表面上,看角块的奇偶就能看见。这正是它适合拿来当教具的原因:还原方法走的也是这一类路子,把群一层一层缩小,第五节的子群链和第六节的陪集都是这样。

9. 小结

最后看一遍状态数(第二节数过的那两个数)的那个乘积(附录 B)。角和棱的位置给出 8!⋅12!8!\cdot12!,朝向给出 373^7 和 2112^{11},最后那个二分之一来自奇偶必须配对。和不加限制的数法相比,383^8 少成 373^7,2122^{12} 少成 2112^{11},再除以 2,正是第二节那个 3×2×23\times2\times2。每一个因子都对应一件具体的事:块能去哪里,块能朝哪个方向,以及哪些交换是被禁止的。

三个守恒量,六个生成元,一条子群链,二十步。这一集就是这几样东西,没有别的。

最后回到第零节那个魔方。那个角被扭过一格,把八个角各自扭了几格加起来,除以三余一,不是零。它当然可以被扭回去,用手把那个角扭回一格就行。它到不了的是另一条路:六个面转,无论接多少步,都到不了它那里。它不是一道很难的题,它根本不在这盘棋里。


附录

附录 A · 群、生成元、群作用

本附录提供的词是:群、生成元、置换、轮换与轮换分解、阶、群作用,以及”所有摆法也构成一个群”这一步。其余术语在用到它的附录里定义(符号 sign 在 C,正规子群在 F)。 每条结论后面配一个能自己算的例子;所有数字由程序生成,不是手抄的。

A.1 从”可以撤销的动作”开始

在魔方上能做的事,都有一个共同的性质:做完可以撤销。把右面顺时针转九十度,再逆时针转九十度,魔方回到原样。

把这类动作收在一起,就得到了一个群。群这个词只要求四件事,每一件在魔方上都看得见:

要求名字在魔方上是什么
两个动作接起来仍是一个动作封闭先转右面再转上面,整体也是一个可撤销的动作
接的顺序分组不影响结果结合(ab)c(ab)c 与 a(bc)a(bc) 是同一串转动,括号只是断句
有一个”什么都不做”单位元放着不动
每个动作都有撤销它的那个动作逆元顺时针九十度的逆是逆时针九十度

注意群只要求”接起来”有意义,不要求可交换:先转右面再转上面,和先转上面再转右面,结果不同。魔方就是一个不可交换的群,而这正是它有内容的原因。

A.2 六个生成元

魔方上的基本动作只有六个:转六个面。记作 U,D,L,R,F,BU,D,L,R,F,B(上、下、左、右、前、后),加一撇表示反方向(R′R'),加 22 表示转一百八十度(写作 R2R2,也常写成 R2R^2;后面的公式一律用 R2R2)。

由这六个动作接出来的所有动作,构成的群记作

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

尖括号读作”由……生成”:括号里那几个叫生成元,GG 里每个元素都是它们的有限串。

算例(RR 到底动了什么,由程序生成)。把六个面的五十四张贴纸编号 00–5353,转一次 RR 之后,贴纸的位置这样搬动:

(2  20  29  51)(5  23  32  48)(8  26  35  45)(9  15  17  11)(10  12  16  14)(2\;20\;29\;51)\quad(5\;23\;32\;48)\quad(8\;26\;35\;45)\quad(9\;15\;17\;11)\quad(10\;12\;16\;14)

附录 A 图:五十四张贴纸的编号,以及一次 R 动到的那二十张

图 A:把魔方摊开成六块的样子,每格里的数字就是这张贴纸的编号。带彩色角标的二十张,是一次 RR 会动到的;角标上的数字表示它属于下面五条轮换里的哪一条。右面正中那张(13 号)没有角标,它是不动点。这张图由生成附录数字的同一份代码画出。

括号里的写法叫轮换,这里按「现在这一格里的贴纸是从哪一格来的」读:22 这一格现在是原来 2020 的贴纸,2020 这一格是原来 2929 的,2929 是原来 5151 的,5151 是原来 22 的。换成「贴纸去了哪」就反过来:22 上的贴纸去 5151,5151 去 2929,2929 去 2020,2020 回到 22。拿实物核对时认准这一点:转一次 RR,顶面靠右那一列是往后面走的,前面靠右那一列是往上走的。一次 RR 动了 20 张贴纸,恰好是五条长度为 44 的轮换。这 20 张分两部分:右面自己的 8 张,以及四周被带走的 12 张。右面中心那张贴纸的位置不变,在置换里它是一个不动点;物理上那块中心确实在原地转了,只是从贴纸的颜色上看不出来。

A.3 置换、轮换分解、元素的阶

上面那种”哪个位置去哪个位置”的对应叫置换。把一个置换拆成互不相交的轮换,叫轮换分解。分解是唯一的,不过”唯一”要说清楚:不计这些轮换写下来的先后,也不计每条轮换从哪个元素起写(上面那五条,我各自选了一个起点)。在这个意义下它是唯一的,所以它是一个动作的指纹。

一个动作重复多少次回到原样,叫它的阶。 阶不是神秘的数:每条轮换各自转回原位所需的次数就是它的长度,全部同时回位的最小次数就是这些长度的最小公倍数。

算例(三行,全部实算)

动作动了几张贴纸轮换长度最小公倍数 = 阶
RR204,4,4,4,44,4,4,4,444
R UR\,U323,7,7,153,7,7,15105105
R U RR\,U\,R322,2,5,5,6,6,62,2,5,5,6,6,63030

看第二行:RURU 要重复 105 次才回到原样,而 105=3⋅5⋅7105=3\cdot5\cdot7 就摆在那三个轮换长度里(15=3⋅515=3\cdot5)。这个数不用猜,是直接数出来的。

第三行是对照:R U RR\,U\,R 只比第二行多接一个 RR,阶却是 3030。多接一步,阶就可以差很多;所以阶要逐个去数,不能看公式长得像就猜。

A.4 群作用:动作和状态是两件事

最后一个词,也是后面几个附录反复要用的:群作用。

GG 里的元素是动作;魔方摆成的样子是状态。一个动作作用在一个状态上,给出另一个状态。从还原态出发,GG 里的每个动作各给出一个状态,能这样得到的状态就叫”拧得出来的”。

把这两件事分清楚有直接的用处。设想把一个角块抠下来、原地扭一格再装回去:得到的状态当然存在,你手上就是它;但它不是任何一串转动作用在还原态上的结果,所以它不在”拧得出来”的那些状态里。

有一个说法要避免:不能说那个状态”没有逆”。把它抠下来扭回去就复原了,所以作为一个摆法它当然可逆。它缺的不是逆,是到达的路径:六个面转,无论接多少步,都到不了它那里。附录 C 会把这句直觉变成一个可以算的判据。

还有一步要在这里交代,否则后面会突然多出一个对象。摆法本身也能接起来:先按一种摆法把块摆好,再按另一种摆法重排一次,结果仍是一种摆法。于是所有摆法也构成一个群,附录 B 数的就是它的大小;而”拧得出来”的那些动作组成的 GG,坐在它里面。C 算出的那个 12 和 F 说的”那三个量分的是更大的那个集合”,都是指这件事。

后面的附录里,这一节的词是这样接下去用的:B 数的是状态的个数;C 定义的三个量是状态的函数,而它们在 GG 的每个动作下不变;E 把 GG 按一个子群切开,切出来的块叫陪集;F 问 GG 内部能不能再拆。


附录 B · 把状态数数出来

这一节要干什么。 正文 §2 说,不加限制地数出来的状态数是真值的 12 倍。这里把两个数都数出来,并把 12 这个比值算准;至于这 12 是从哪来的,是附录 C 的事。

先说清楚”一个状态”指什么

把魔方拆开,能拆出三种块:8 个角块(三种颜色)、12 个棱块(两种颜色)、6 个中心块(一种颜色)。中心块彼此之间不会换位,它们只在原地转,所以六个中心确定了”哪一面该是什么颜色”,我们就用它们当坐标系,不再计入状态。

于是一个状态由四件事决定:

  1. 8 个角块分别落在哪个角位上;
  2. 每个角块在自己的位置上转到了第几格(角位有三张贴纸,角块的某张指定贴纸可以落在其中任意一张的位置上);
  3. 12 个棱块分别落在哪个棱位上;
  4. 每个棱块翻没翻(棱位有两张贴纸)。

第 1 条和第 3 条各是一个置换(permutation):把 8 个块一一对应到 8 个位置上的一种排法,没有两个块落在同一个位置。第 2 条叫朝向(orientation),第 4 条叫翻转(flip),本附录只要数个数,它们的精确定义放在附录 C。

不加限制地数

四件事分别数,再相乘:

8!  ⋅  38  ⋅  12!  ⋅  212.8!\;\cdot\;3^{8}\;\cdot\;12!\;\cdot\;2^{12}.

逐项的来历:8 个角块排进 8 个角位有 8!8! 种排法;每个角块各有 3 格朝向,8 个角块就是 383^8;棱同理,12!12! 和 2122^{12}。

算例(逐位算出来):

因子值
8!8!40 320
383^{8}6 561
12!12!479 001 600
2122^{12}4 096
乘积519 024 039 293 878 272 000 ≈5.19×1020\approx 5.19\times10^{20}

真正能拧出来的状态数

∣G∣=8!⋅37⋅12!⋅2112=43 252 003 274 489 856 000≈4.33×1019.|G| = \frac{8!\cdot 3^{7}\cdot 12!\cdot 2^{11}}{2} = 43\,252\,003\,274\,489\,856\,000 \approx 4.33\times10^{19}.

这个式子里有三处收缩:383^8 变成 373^7、2122^{12} 变成 2112^{11}、最后再除以 2。

算例(把比值算出来):

8!⋅38⋅12!⋅2128!⋅37⋅12!⋅211/2=3×2×2=12,\frac{8!\cdot 3^{8}\cdot 12!\cdot 2^{12}}{8!\cdot 3^{7}\cdot 12!\cdot 2^{11}/2} = 3\times 2\times 2 = 12 ,

两个大数相除也是同一个结果:519 024 039 293 878 272 000÷43 252 003 274 489 856 000=12519\,024\,039\,293\,878\,272\,000 \div 43\,252\,003\,274\,489\,856\,000 = 12,余数为 0(本文实算)。

对照(这个比值会不会不管填什么都是 12):把 373^7 误写成 383^8,右边变成 129 756 009 823 469 568 000129\,756\,009\,823\,469\,568\,000(正好是 ∣G∣|G| 的 3 倍),比值就成了 4,与 ∣G∣|G| 也不等。所以上面那个”整 12”不是凑出来的。

这 12 不是一个笼统的修正系数,而是三个独立的因子 3×2×23\times2\times2。 每个因子对应一条”做不到”,三条各自是一个守恒量。附录 C 把这三个量写出来,并证明它们确实不动。


附录 C · 三个守恒量

这一节要干什么。 把附录 B 里的 3×2×23\times2\times2 兑现成三个具体的量:每个量都是一个可以从状态直接算出来的数,任何一次转动都不改变它。有了它们,“只扭一个角""只翻一个棱""只换两块”这三件事就一句话讲清:它们改变了不该变的量。

把朝向和翻转定下来

要算数,先得把”转到第几格""翻没翻”定义到可以逐块读出来。

角的朝向。 每个角位贴着三张贴纸。把这三张按从外面看逆时针的顺序排好,并且让贴在 U 面或 D 面的那张排在第一位(每个角位恰好贴着 U 或 D 之一)。每个角块也有一张指定贴纸:它在还原状态下贴在 U 或 D 面的那一张。朝向 oo 就是这块的指定贴纸现在落在所在角位的第几张上,取值 0、1、2。

棱的翻转。 每个棱位贴着两张贴纸,指定其中一张为”主位”:若该棱位贴着 U 或 D,取那一张;其余四个中层棱位取贴着 F 或 B 的那一张。每个棱块同样有一张主贴纸(按它还原时所在的棱位定)。翻转 ff 为 0 表示主贴纸落在主位上,为 1 表示落在另一张上。

这两条定义只用到”哪张贴纸在哪”,读者拿一个实物魔方就能逐块读出来。

三个量

设一个状态为 (p,o,q,f)(p, o, q, f):pp 是角的置换,o=(o1,…,o8)o=(o_1,\dots,o_8) 是八个角的朝向,qq 是棱的置换,f=(f1,…,f12)f=(f_1,\dots,f_{12}) 是十二个棱的翻转。定义

σ=∑i=18oi mod 3,τ=∑j=112fj mod 2,sgn=sign⁡(p)⋅sign⁡(q).\sigma = \sum_{i=1}^{8} o_i \bmod 3,\qquad \tau = \sum_{j=1}^{12} f_j \bmod 2,\qquad \mathrm{sgn} = \operatorname{sign}(p)\cdot\operatorname{sign}(q).

 mod 3\bmod 3 的意思是只保留除以 3 的余数:0,1,20,1,2 三个值,且 2+2=12+2=1。置换的符号 sign⁡\operatorname{sign} 这样定义:把一个置换拆成若干次”交换两块”的连续操作,拆法不唯一,但次数的奇偶性是唯一的;偶数次记 +1+1,奇数次记 −1-1。例如把四块转一圈(一个 4-轮换)需要三次交换,符号是 −1-1。

一次转动对这三个量做了什么

任取一个面转 90°,比如 RR。它把四个角位上的块转一圈、四个棱位上的块转一圈,别的块不动。算例(六个生成元逐个读出来,本文实算):

转动角上的 4-轮换角的朝向增量棱上的 4-轮换棱的翻转增量
UU(UBL ULF UFR URB)全 0(UL UF UR UB)全 0
DD(DLB DBR DRF DFL)全 0(DL DB DR DF)全 0
RR(DBR URB UFR DRF)1,2,1,21,2,1,2(DR BR UR FR)全 0
LL(DLB DFL ULF UBL)2,1,2,12,1,2,1(DL FL UL BL)全 0
FF(DFL DRF UFR ULF)2,1,2,12,1,2,1(FL DF FR UF)四个棱各翻 1
BB(DLB UBL URB DBR)1,2,1,21,2,1,2(BL UB BR DB)四个棱各翻 1

逐条读这张表:

三个量都不动。而且注意,不是”每块都不动”,是”加起来不动”:FF 明明翻了四个棱,τ\tau 仍然不变。这正是守恒量的意思。

从一次转动推到任意一串转动

上一段只查了六个生成元。要推到任意状态,需要一条性质:这三个量在”把两串转动接起来”时是相加(相乘)的。

先把话说准。两个状态接起来仍是一个状态:先按 yy 摆一次,再按 xx 摆一次。这时新状态的角朝向是

oix∘y=oy(i)x+oiy(mod3),o^{x\circ y}_i = o^{x}_{y(i)} + o^{y}_i \pmod 3 ,

这里 oo 按块编号,y(i)y(i) 是块 ii 经过 yy 之后所在的位置:块 ii 先带着自己在 yy 里得到的朝向 oiyo^{y}_i 去了位置 y(i)y(i),再被 xx 在那个位置上加了一格 oy(i)xo^{x}_{y(i)}。八项求和时,yy 只是把 oxo^x 的八个数重新编了号,求和与编号无关,于是

σ(x∘y)=σ(x)+σ(y)(mod3).\sigma(x\circ y) = \sigma(x) + \sigma(y) \pmod 3 .

同样的算法给出 τ(x∘y)=τ(x)+τ(y) mod 2\tau(x\circ y) = \tau(x)+\tau(y) \bmod 2;而置换的符号本来就满足 sign⁡(p1p2)=sign⁡(p1)sign⁡(p2)\operatorname{sign}(p_1p_2)=\operatorname{sign}(p_1)\operatorname{sign}(p_2),所以 sgn\mathrm{sgn} 也是相乘的。

一个映射如果像这样”把接起来变成加起来(乘起来)“,就叫同态(homomorphism)。把三个量打包成一个映射

Φ:(p,o,q,f)  ⟼  (σ, τ, sgn)  ∈  Z/3×Z/2×{±1},\Phi: (p,o,q,f)\;\longmapsto\;(\sigma,\ \tau,\ \mathrm{sgn})\;\in\;\mathbb{Z}/3\times\mathbb{Z}/2\times\{\pm1\},

它就是一个同态,右边一共 3×2×2=123\times2\times2 = 12 个值。

于是:每个生成元的 Φ\Phi 值都是 (0,0,+1)(0,0,+1);任何一串转动都是生成元接起来;同态把”接起来”变成”加起来”,加的都是 0。所以任何拧得出来的状态,Φ\Phi 值都是 (0,0,+1)(0,0,+1)。

算例(300 步随机拧,本文实算):从还原态出发随机拧 300 步,每一步之后读一次 (σ,τ,sgn)(\sigma,\tau,\mathrm{sgn}),300 次全是 (0,0,+1)(0,0,+1)。

三件做不到的事

附录 C 图:三个做不到的状态,每个只破坏三个守恒量里的一个

图 C:把一个还原好的魔方用手改坏,三种改法各一栏。红框标出被动过的贴纸,下面三格是同一组读数 σ\sigma、τ\tau、sgn\mathrm{sgn}。每一栏里恰好只有一个数离开了守恒值,那个数就是这种改法做不到的理由。第三栏只有两张贴纸变色,是因为被对调的两张朝上贴纸都是白的,那一半的交换在颜色上看不出来。这张图由计算附录 C 那三个量的同一份代码画出。

反过来用:只要算出某个状态的 Φ\Phi 值不是 (0,0,+1)(0,0,+1),它就一定拧不出来。

算例(三个状态,逐个算,本文实算):

手动改出来的状态σ\sigmaτ\tausgn\mathrm{sgn}结论
把 UFR 那个角原地扭一格,别的不动110+1+1σ≠0\sigma\neq0 ⟹ 拧不出来
把 UR 那个棱原地翻一下,别的不动011+1+1τ≠0\tau\neq0 ⟹ 拧不出来
把 UR 和 UF 两个棱对调,别的不动00−1-1sgn≠+1\mathrm{sgn}\neq+1 ⟹ 拧不出来

第一行正是 §0 里那个被扭过角的魔方:它不是”很难还原”,是不可能还原:差的那一格在 σ\sigma 上留下了 11,而任何转动都不能把 11 变回 00。

(把角往另一个方向扭一格,σ\sigma 读作 22;22 同样不是 00,结论一样。)

12 从哪来

现在可以回答附录 B 留下的问题。不加限制数出来的那 5.19×10205.19\times10^{20} 个摆法,构成一个集合 SS;Φ\Phi 把 SS 映到 12 个值上。

∣G∣≤∣S∣12=43 252 003 274 489 856 000.|G| \le \frac{|S|}{12} = 43\,252\,003\,274\,489\,856\,000 .

这里证到哪。 上面证到的是"≤\le":三个守恒量排除了 11/12 的摆法。反过来的一半:凡是三个量都对的摆法,都真的能拧出来。本附录没有证。它需要的是一套构造:能把任意三块转一圈而不动其他块的公式(附录 D 的三轮换),以及只调朝向的公式。有了这套工具,就能把任何 Φ=(0,0,+1)\Phi=(0,0,+1) 的状态一步步复原,从而 ∣G∣=∣S∣/12|G| = |S|/12 取等号。附录 D 给出其中的三轮换(只调角朝向的一个例子在附录 F);把它们接成一条对任意状态都走得通的路线,是正文 §5 提到的四段链所做的事(出处见文末来源 6),本文没有把那条路线走一遍。


附录 D · 换向器与共轭:把作用范围缩小

这一节要干什么。 附录 C 证到的是一半:三个守恒量排除掉了十二分之十一的摆法。要把 ≤\le 收成 ==,需要反过来的能力:任意给一个三个量都对的状态,都能拧回去。本节造两件工具:共轭和换向器。它们是所有还原方法的引擎,也是那一半的构造材料。

一次转动动多少块

先看一个数:RR 转 90°,动了 4 个角块 + 4 个棱块 = 8 块(本文实算)。UU 也是 8 块。任何一个面转都是 8 块。

难处就在这里:要把最后两三块摆好,可用的每一招都会顺手动 8 块。所以问题不是”会不会拧”,是”能不能只动想动的那几块”。

共轭:同一招,换个地方使

设 AA 是一串转动,XX 是另一串。把

XAX−1X A X^{-1}

读成三步:先做 XX 把想动的块送到 AA 够得着的地方,再做 AA,最后用 X−1X^{-1} 把场景还原回去。净效果是:AA 那一招原封不动,只是换了作用对象。

算例(本文实算)。取

A=R B′ R F2 R′ B R F2 R2,A = R\,B'\,R\,F2\,R'\,B\,R\,F2\,R2 ,

它是一个纯角三轮换:只把三个角块转一圈,不动任何棱块,也不留下扭转(它和换向器的关系见后面「还差一步:朝向」)。实算读数:

公式阶动的角块动的棱块
AA3ULF, URB, UFR无
UAU−1U A U^{-1}3UBL, URB, UFR无

同样是”三个角转一圈”,但换了一个三元组:AA 动的那个 ULF 被换成了 UBL,另外两个不变。这就是共轭:招式不变,对象换了。读者想动哪三个角,就找一个 XX 把它们送到 AA 的三个位置上。

(一个细节,留给较真的读者:若把上面的 UU 换成 FF,得到的三轮换会带上扭转。原因是附录 C 里”朝向”是相对 U/D 面定义的,FF 会改变这个参照。换句话说,共轭保持”置换的形状”,但朝向要重新换算。)

换向器:让两招互相抵消,只剩交集附近的几块

设 AA、BB 各是一串转动。换向器定义为

[A,B]=A B A−1 B−1.[A, B] = A\,B\,A^{-1}\,B^{-1} .

读法:做 AA,做 BB,撤销 AA,撤销 BB。如果 AA 和 BB 各自动的块几乎不重叠,那么撤销的两步几乎把一切都还原:留下差异的只有少数几块:落在两者共同范围里的块,以及被这两招带进、带出这个范围的块。

算例(本文实算):取 A=R U R′A = R\,U\,R',B=DB = D。

公式动的块数具体
R U R′R\,U\,R'8角 UBL, ULF, DRF, UFR;棱 UL, UB, UF, FR
DD8角 DLB, DFL, DBR, DRF;棱 DL, DB, DF, DR
[R U R′, D][R\,U\,R',\,D]3角 DFL, DRF, UFR;棱 无

两招各动 8 块,合起来的换向器只动 3 块。它们的角块范围只共有一个 DRF,留下的差异正好围绕这个交集。

换向器把作用范围从”八块”压到”三块”。

还差一步:朝向

[R U R′, D][R\,U\,R',\,D] 只动三个角、不碰棱,但实算读数显示:其中两个角带着扭转(DRF 扭 1、UFR 扭 2)。所以它还不是”干净”的三轮换。

这正好是附录 C 那三个量在这里的回声:位置和朝向是两件独立的事,换向器先解决了位置,朝向还得另外还。把 AA、BB 换掉再试,就能把扭转也压掉,上面那个 A=R B′ R F2 R′ B R F2 R2A = R\,B'\,R\,F2\,R'\,B\,R\,F2\,R2 就是结果:3 个角、0 个棱、0 扭转。

配对的棱版本同样实算过:

R2 U R U R′ U′ R′ U′ R′ U R′:阶 3,只把三个棱块转一圈,不动任何角块,不带翻转。R2\,U\,R\,U\,R'\,U'\,R'\,U'\,R'\,U\,R' \quad\text{:阶 3,只把三个棱块转一圈,不动任何角块,不带翻转。}

阶:一串转动重复多少次回到原位

把同一串转动反复做下去,总会回到还原态(状态有限,且每一步都可撤销)。次数叫这串转动的阶(order)。

算例(全部本文实算):

公式阶
R UR\,U105
R U RR\,U\,R30
R U R′ U′R\,U\,R'\,U'6
R′ D′ R DR'\,D'\,R\,D6
R U R′ U′ R′ F R F′R\,U\,R'\,U'\,R'\,F\,R\,F'3
R B′ R F2 R′ B R F2 R2R\,B'\,R\,F2\,R'\,B\,R\,F2\,R23

⚠️ 阶是 3 不等于”它是一个三轮换”。 上表最后两行阶都是 3,但读数不同:R B′ R F2 R′ B R F2 R2R\,B'\,R\,F2\,R'\,B\,R\,F2\,R2 只动 3 个角;而 R U R′ U′ R′ F R F′R\,U\,R'\,U'\,R'\,F\,R\,F' 同时动 3 个角和 3 个棱(两个角带扭、两个棱带翻)。阶为 3 只说明”做三次回到原位”,角的三轮换和棱的三轮换乘在一起同样满足。想要”只动三块”,必须直接去读动了哪些块。

这套工具接回附录 C

三轮换是偶排列:把三块转一圈等于两次对换。所以无论怎么拼三轮换,sgn\mathrm{sgn} 始终是 +1+1,和附录 C 的守恒量完全一致,永远拼不出”只换两块”。

反过来,有了纯三轮换(角、棱各一个)加上只调朝向的公式,就能把任意一个三个量都对的状态一步步复原:若角的排列和棱的排列都是奇的(sgn=+1\mathrm{sgn}=+1 允许这种情况,转一次面就是),先转一次面把两者同时变成偶的;然后用三轮换把位置摆对,再调朝向。这就是附录 C 末尾那条边界的补齐方向;把它走成一条对任意状态都成立的完整路线,是正文 §5 提到的四段链(来源 6)做的事,本文只指出方向。

正文 §4 那次完整还原

打乱(从还原态出发,二十五步,本文实算):

D′ R′ L U′ B2 R D2 U′ B′ F U′ L′ U2 F′ U2 B2 L′ U′ R F′ U′ L U′ F′ U′D'\,R'\,L\,U'\,B2\,R\,D2\,U'\,B'\,F\,U'\,L'\,U2\,F'\,U2\,B2\,L'\,U'\,R\,F'\,U'\,L\,U'\,F'\,U'

按官方八步拧回去,每步的转动(同一步里相邻的同面转动已合并;第 6 步照公式完整做两遍,接缝处不合并):

合计 118 步。校验:打乱接上这 118 步,每一块回到原位、朝向全对。动画按这八段画。


附录 E · 子群、陪集与拉格朗日:2010 年那次证明

这一节要干什么。 用一个真实例子讲清”子群”和”陪集”:2010 年证明”任何状态 20 步以内可还原”的那次计算,本身就是一次陪集分解。所有数字都能自己核。

子群

子群(subgroup) 指群里一个自身封闭的子集:里面任意两个元素接起来还在里面,每个元素的逆也在里面。

本节的主角是这一个:

H=⟨ U, D, R2, L2, F2, B2 ⟩H = \langle\, U,\ D,\ R2,\ L2,\ F2,\ B2 \,\rangle

这个群只允许上下两面随便转,其余四面只能转 180°。尖括号表示”由这些转动生成”:把它们任意接起来能得到的全部状态。这是科先巴(Herbert Kociemba)两阶段解法里的那个中间集合。

∣H∣|H| 是多少(算例,逐项算):在 HH 里,

这四条只说明 HH 里的状态不可能更多;这些排法确实都生成得出来、等号成立,本文没有证,取等号引自来源 1(cube20.org 给出的每个陪集 19 508 428 800 个状态)。

∣H∣=8!⋅8!⋅4!2=40320×40320×242=19 508 428 800.|H| = \frac{8!\cdot 8!\cdot 4!}{2} = \frac{40320 \times 40320 \times 24}{2} = 19\,508\,428\,800 .

陪集

固定一个状态 gg。先按 HH 里任意一个元素摆,再接着做 gg,得到的一堆状态记作 HgHg,叫 gg 的陪集(coset)。(符号按公式的写法读,从左到右就是先后;先后要紧:HH 在前、gg 在后。反过来「先 gg 再 HH」得到的是另一堆,下面那句「离 HH 一样远」对它不成立,RR 和 R UR\,U 就是一对反例:一个一步回到 HH,一个至少两步。)

两个陪集要么完全重合,要么毫无交集,而且每个陪集和 HH 一样大。这两条合起来就是拉格朗日定理:(这两条第二集用 S3S_3 和 A3A_3 演过一遍,第三集给了完整证明;这里只是把那套做法用到一个大得多的群上。)

∣G∣=(陪集个数)×∣H∣.|G| = (\text{陪集个数}) \times |H| .

算例(本文实算):

∣G∣∣H∣=43 252 003 274 489 856 00019 508 428 800=2 217 093 120\frac{|G|}{|H|} = \frac{43\,252\,003\,274\,489\,856\,000}{19\,508\,428\,800} = 2\,217\,093\,120

余数为 0。反过来乘也对:2 217 093 120×19 508 428 800=∣G∣2\,217\,093\,120 \times 19\,508\,428\,800 = |G|。

对照:把每个陪集的大小改成 19 508 428 801,乘积就不再等于 ∣G∣|G|:这条等式不是恒真的。

2010 年那次证明就是这样切的

把整个魔方群按 HH 切成 2 217 093 120 个陪集 HgHg。同一个陪集里的状态,拧回 HH 所需的转动是同一批:x=h gx = h\,g 时,x m∈Hx\,m \in H 当且仅当 g m∈Hg\,m \in H,与 hh 无关。所以「离 HH 多远」是整个陪集共有的一个数。于是证明”任何状态 20 步以内”这件事,就不必逐个检查 4.3×10194.3\times10^{19} 个状态,只需要对每个陪集给出一个上界。

原文(cube20.org/How We Did It)给出的三个数:

数值本文核对
陪集个数2 217 093 120与 ∣G∣/∣H∣\vert G\vert/\vert H\vert 相符
每个陪集的大小19 508 428 800与 8!⋅8!⋅4!/28!\cdot8!\cdot4!/2 相符
利用对称性与集合覆盖后真正要算的陪集数55 882 296占全部陪集的 2.52%

最后一行是这次计算能做完的原因:魔方有 48 种对称(旋转加镜像),再加上一个陪集的结果可以覆盖其他陪集,真正需要动手的只剩 2.52%。

算例:55 882 296÷2 217 093 120=2.5205%55\,882\,296 \div 2\,217\,093\,120 = 2.5205\%(本文实算)。

与正文 §5 的关系

正文 §5 讲的 Thistlethwaite 四段法,是同一个想法的更早版本:不是一个子群,而是一条子群链,每一段把问题限制到更小的子群里。HH 等价于这条链上的第二站:Thistlethwaite 让左右两面自由转、其余四面只转一百八十度,科先巴把自由的两面换成上下,他自己说两者等价。四段法把”还原”变成”逐段进入更小的子群”,而 2010 年的证明把”数步数”变成”逐个陪集给上界”。


附录 F · 魔方群不是单群

这一节要干什么。 整个系列的主线是单群:不能再往下拆的那种群。魔方群 GG 不是单群:它能拆。这里给出一个具体的见证,并逐条验证它满足定义。

两个词

正规子群(normal subgroup):GG 的一个子群 NN,如果对任意 g∈Gg\in G 都有

gNg−1=N,gNg^{-1} = N ,

就称 NN 是正规的。读法:把 NN 里的操作换个地方做(附录 D 的共轭),得到的还在 NN 里:这一堆操作整体换个地方做,还是这一堆。

单群(simple group):只有两个正规子群(只含单位元的那个,和它自己)的群。也就是拆不动。(这两个词第三集都定义过,并用 S3S_3 的 Cayley 表把「按正规子群切块、块与块之间怎么乘」画了出来;这里直接取用。)

一条走不通的路(先把它说清楚)

最顺手的想法是用附录 C 的三个守恒量:每个量不是都给出”不改变它的那些操作”吗?

这条路不通。 σ\sigma、τ\tau、sgn\mathrm{sgn} 是定义在全部摆法的群 SS 上的同态。在拧得出来的状态里,三个量本来就全在守恒值 (0,0,+1)(0,0,+1) 上(附录 C 的结论)。所以”不改变 σ\sigma 的操作”在 GG 里是全部操作,什么也没分出来。

换句话说:这三个量分的是更大的那个集合 SS,魔方群只是其中的十二分之一;它们把 GG 圈进了 SS 的一个正规子群(两者相等,要靠附录 C 没有证的那一半),但对 GG 内部的结构一句话也没说。

见证:只看角块排列的奇偶

附录 C 里的第三个量是两个符号的乘积:sign⁡(角排列)⋅sign⁡(棱排列)\operatorname{sign}(\text{角排列})\cdot\operatorname{sign}(\text{棱排列}),它在 GG 上恒为 +1+1。

但单看其中一半就不是常数了。 定义

ε:G⟶{±1},ε(g)=sign⁡(g 的角块排列).\varepsilon: G \longrightarrow \{\pm1\},\qquad \varepsilon(g) = \operatorname{sign}(g\ \text{的角块排列}) .

于是 N={ g:ε(g)=+1 }N = \{\,g : \varepsilon(g) = +1\,\},也就是角块排成偶排列的那些操作,是 GG 的正规子群,指数为 2。GG 被它切成两半,一半是 NN,另一半是 RR 那样的奇操作。

说得直白些:把角块排成偶排列的那些操作自成一堆;任何操作把这一堆整个换个地方做,还是这一堆。

逐条验证定义(算例,本文实算)

要验的做法结果
与附录 C 一致200 个随机元素,比较”角符号 × 棱符号”恒为 +1+1,违例 0(同态性不用测:置换的符号本来就是相乘的)
满射算 ε(R)\varepsilon(R)、ε(R2)\varepsilon(R^2)、ε(id)\varepsilon(\mathrm{id})−1-1、+1+1、+1+1 ⟹ 两个值都取到
gNg−1=NgNg^{-1}=N取 n=R2∈Nn = R^2 \in N,用 60 个随机 gg 做 gng−1gng^{-1}60 次全部仍在 NN 里
对照取奇元素 R∉NR\notin N,同样共轭 60 次60 次全部仍是奇 ⟹ 这个检查会报错,不是恒真

最后一行说明这项检查分得出里外:奇的元素共轭之后仍然是奇的,不会被算进 NN。

第二个见证:把十二个棱全部翻一遍

还有一个更小的正规子群,只有两个元素:单位元,和把 12 个棱块全部原地翻转的那个状态(叫 superflip)。

它可以用 20 步做出来,下面这条公式取自来源 1:

R L U2 F U′ D F2 R2 B2 L U2 F′ B′ U R2 D F2 U R2 UR\,L\,U2\,F\,U'\,D\,F2\,R2\,B2\,L\,U2\,F'\,B'\,U\,R2\,D\,F2\,U\,R2\,U

本文实算:这条公式确实只翻 12 个棱、不动任何角、也不改变任何块的位置;它在 GG 里;它与六个生成元以及 60 个随机元素全部可交换(先做它再做别的,与先做别的再做它,结果相同);它自己做两次回到还原态。

可交换是这里唯一的新词,而它正好给出正规性:若 nn 与所有 gg 可交换,则 gng−1=ngng^{-1} = n,这堆东西当然还是原来那堆。

第三个见证:只扭不换位的那些操作

还有一个看起来最自然的候选:把每块都放回原位、只是有些块转了一格的那些操作。它是正规的(它是”忘掉朝向,只看位置”这个同态的核),而且能举出一个成员(本文实算):

(R′ D′ R D)2  U  (R′ D′ R D)4  U′(R'\,D'\,R\,D)^2\;U\;(R'\,D'\,R\,D)^4\;U'

二十六步做完,二十块全部在原位、没有一条棱翻转,只有 UFR 扭了一格、URB 反向扭了一格(1+2=3≡01+2=3\equiv0,正合附录 C 的 σ\sigma);它的阶是 3。所以这个核不只含单位元,是 GG 的第三个非平凡正规子群。

它为什么找得到:R′D′RDR'D'RD 做两遍只把 UFR 扭一格、把下层弄乱;中间的 UU 换另一个角到同一个位置;再做四遍把那个角扭两格,而六遍之和正好是 R′D′RDR'D'RD 的阶,下层的乱恰好还回来。

落点

魔方群能拆:ε\varepsilon 把它切成两半,superflip 给出一个两元素的正规子群(它落在中心里;中心恰好只有这两个元素是已知结果,本文只核了前一半),纯扭转给出第三个正规子群。它不是单群。 系列主线里那些单群(尤其是魔群)是拆不动的;魔方群不是它们中的一员,而恰恰是这种”可拆”让它成为一个好教具:还原方法走的是同一类路子,把群一层层缩小(正文 §5 的子群链,附录 E 的陪集)。


附录 G · 推广到 nn 阶

这一节要干什么。 正文 §7 问”到多少阶就解不开”。这里把三阶的三个守恒量逐条放到四阶去看(更高的阶只谈步数):哪一条仍然成立、哪一条根本没有对应物、哪一条失效了。落点是一句话:三条”做不到”里,有两条是三阶的性质,不是魔方的性质;扭角那一条在四阶照旧成立。

块的种类随 nn 变

nn 阶魔方拆开有三类块:

两处与三阶不同,后面都要用到:

  1. nn 为偶数时没有固定中心。 三阶的六个中心互不换位,定义了”哪一面是什么颜色”;四阶的 24 个中心全都会动。
  2. 同色的中心块彼此不可区分。 四个白色中心互换,看起来完全一样。

四阶的状态数

逐项数(算例,本文实算):

部分数目来历
角的位置与朝向8!⋅378!\cdot 3^{7}8 个角任意排(包括奇排列),7 个角的朝向自由、第 8 个被唯一确定
24 个翼块24!24!任意排,包括奇排列;翼块无法单独翻转
24 个中心块24!/(4!)624!/(4!)^{6}任意排,但每种颜色的 4 个不可区分
整体朝向÷ 24\div\,24没有固定中心,整块立方体的 24 种摆向看起来一样
8!⋅37⋅(24!)2247=7 401 196 841 564 901 869 874 093 974 498 574 336 000 000 000≈7.40×1045.\frac{8!\cdot 3^{7}\cdot (24!)^2}{24^{7}} = 7\,401\,196\,841\,564\,901\,869\,874\,093\,974\,498\,574\,336\,000\,000\,000 \approx 7.40\times10^{45} .

(247=(4!)6×2424^7 = (4!)^6\times 24:六次方来自六种颜色,最后那个 24 来自整体朝向。)

辛马斯特(David Singmaster) 1982 年就给出了同一个结果 [1],他的写法是 8!⋅24!⋅24!⋅38/(3⋅247)8!\cdot24!\cdot24!\cdot3^8/(3\cdot24^7)(与上式相同,因为 38/3=373^8/3 = 3^7),后面跟着同样这 46 位数字。本文是先自己逐项算出来,再回去核对他的原文。

三个守恒量逐条过

附录 G 图:三个守恒量在三阶与四阶上各读一次

图 G:同样三个量,在三阶和四阶上各读一次。上半是块的种类与数目,每个数都算了两遍(枚举小块 + 闭式),两遍相等。下半是三条守恒量的去向:σ\sigma 两边都成立;τ\tau 在四阶没有对应物,因为翼块根本翻不过来,三阶上那个”翻一个棱”的样子在四阶是一次交换;sgn\mathrm{sgn} 在四阶失效,来路有两个:角的奇排列藏进了同色因而彼此相同的中心块里;三阶的一条棱在四阶成了两块。末行是本附录真正的落点:没有哪一阶”解不开”,长的只是还原所需的步数。

σ\sigma(角的扭转之和  mod 3\bmod 3):仍然成立

四阶的角块仍是三张贴纸的角块,面转仍然按同样的方式扭它们。

算例(本文实算):200 条随机四阶打乱(含内层切片与双层转动),每条算一次 σ\sigma,违例 0。对照:用手把一个角原地扭一格,σ\sigma 读作 1,不是 0。所以这个检查会报错。

这也正是上面计数里 373^7 那一项的来历。

τ\tau(棱的翻转之和  mod 2\bmod 2):没有对应物

三阶的”翻转”是指一个棱块在原位上翻个面。四阶的翼块做不到这件事,理由是物理的:

The 24 edges cannot be flipped, due to the internal shape of the pieces. [2]

那么三阶上”翻一个棱”的样子,在四阶是什么?是把同一条棱上的两个翼块对调。 那是一次置换,不是朝向。所以 τ\tau 在四阶没有对应的守恒量,它的角色被并进了下一条。

sgn\mathrm{sgn}(排列的符号):失效了

三阶上,“只对调两块、别的不动”被 sgn\mathrm{sgn} 排除(附录 C)。四阶能做出看上去一样的事。

算例(本文实算)。在四阶上执行

r2 U2 r2 Uw2 r2 u2r2\ U2\ r2\ Uw2\ r2\ u2

(rr 是从右面数第二层的内层切片,UwUw 是上面两层一起转,uu 是从上面数第二层)。读数:

对照两条:还原态用同一套读法得到 12 条配对、符号 +1+1;只转一次 UU 得到四条棱的轮换、符号 −1-1 且角块没有归位。所以”符号 −1-1“不是这套读法恒给的结果。

在三阶上,这种状态(只有两条棱互换、别的全在家)就是附录 C 表里第三行那一类,被 sgn\mathrm{sgn} 判为拧不出来;这条公式换的是 UF 与 UB 两条。在四阶它拧得出来。

差别在哪。 三阶的一条棱是一块,四阶的一条棱是两块翼块。把两条棱整体对调,在 24 块翼块上是两次交换,是偶排列(本文实算:翼块两次交换,角一块没动,中心块按块算是四次交换,也是偶的)。三阶的 sgn\mathrm{sgn} 之所以拦住它,是因为它把每条棱当成一块来数。所以这个例子里没有什么奇排列被藏起来,是三阶的”一块”到了四阶变成了”两块”。

四阶上另有一种奇排列是真的藏起来了,藏在中心块里:

An odd permutation of the corners implies an odd permutation of the centres and vice versa; however, even and odd permutations of the centres are indistinguishable due to the identical appearance of the pieces. [2]

三阶的六个中心各只有一个,藏不住,于是角的奇排列在外面留下了痕迹,那个痕迹就是 sgn\mathrm{sgn}。四阶同色的四块中心互换看不出来:转一次外层面,角和中心各是一个四轮换(本文实算),中心那一半看不见,角的奇排列就不再有 sgn\mathrm{sgn} 这样的东西拦它。

这句”藏起来”不是修辞,是可操作的:把中心块做成彼此可区分(比如图案魔方),奇的中心排列立刻变得可见,状态数也随之乘回去 [2]。

到多少阶为止

没有”为止”。任何阶都能还原:打乱是一串转动,每一步都可撤销,倒着做回去即可。

真正随 nn 增长的是最坏情况下需要多少步。这个量级是已知的:

Θ ⁣(n2log⁡n),\Theta\!\left(\frac{n^2}{\log n}\right) ,

Demaine 等 2011(arXiv:1106.5736,本文核过摘要原文):上界来自把 Θ(n2)\Theta(n^2) 的常规解法并行,一次转动可以同时处理许多互不相干的块,省下的正是 log⁡n\log n;下界来自计数 [3]。

所以正文 §7 那个问题的答案不是一个阶数,是一条增长律。


参考

[1] D. Singmaster, Cubic Circular, Issue 3 & 4(1982 年春夏)“Rubik’s Revenge — The 434^3” 一节。原文:“the correct (I hope!) answer is 8!⋅24!⋅24!⋅38/(3⋅247)8!\cdot24!\cdot24!\cdot3^8/(3\cdot24^7) = 7 40119 68415 64901 86987 40939 74498 57433 60000 00000 = 7.4×10457.4\times10^{45}“,并说明分母里的 24 来自”六组四个相同中心各有 24 种排法”与”立方体有 24 个无法区分的朝向”。2026-09-20 访问(jaapsch.net 的存档版)。

[2] Wikipedia, Rubik’s Revenge, Permutations 一节(2026-09-20 访问):上面两处引文出自此页,它给出的公式与全数与 [1] 一致,本文用作二手对照。

[3] E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, A. Winslow, Algorithms for Solving Rubik’s Cubes, arXiv:1106.5736. 摘要原文:“we show that the n x n x n Rubik’s Cube … has a ‘God’s Number’ (diameter of the configuration space) of Theta(n^2/log n). The upper bound comes from effectively parallelizing standard Theta(n^2) solution algorithms, while the lower bound follows from a counting argument.”


参考来源

一手

  1. Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge,God’s Number is 20,https://cube20.org/(20 步、约 35 CPU-年、历史表、“How We Did It” 的陪集与对称约化数字)
  2. Tomas Rokicki, Morley Davidson,God’s Number is 26 in the Quarter Turn Metric,https://cube20.org/qtm/(2014 年 8 月、两位作者、约 29 CPU-年、俄亥俄超算中心;已知需要 26 步的状态只有一个,连同它的两个旋转像)
  3. David Singmaster,Cubic Circular Issue 3 & 4(1982),https://www.jaapsch.net/puzzles/cubic3.htm(四阶状态数的原始式子与全数;中心与角的奇偶耦合)
  4. Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow,Algorithms for Solving Rubik’s Cubes,arXiv:1106.5736(n×n×nn\times n\times n 的直径是 Θ(n2/log⁡n)\Theta(n^2/\log n))
  5. Herbert Kociemba,两阶段算法,https://www.kociemba.org/math/imptwophase.htm
  6. Morwen Thistlethwaite 原始打印稿(Singmaster 扫描,Jaap Scherphuis 转录),https://www.jaapsch.net/puzzles/thistle.htm
  7. 匈牙利专利 HU170062B(申请 1975-01-30,公布 1977-03-28,同族标题 “Spatial logic toy”),https://patents.google.com/patent/HU170062B/en
  8. Gathering 4 Gardner 对鲁比克的访谈逐字稿(2018 年录,2019 年发;「不是要做一道谜题」和「一个多月才第一次拧回去」两句的出处,原话 “The cube was not created as a puzzle” 与 “It was more than a month I find my practical solution”),https://www.gathering4gardner.org/an-interview-with-erno-rubik/

二手(用作对照) 9. Rubik’s Revenge,英文维基,https://en.wikipedia.org/wiki/Rubik%27s_Revenge(四阶状态数公式与全数,引 Singmaster;翼块不可单独翻转;同色中心使奇排列不可见) 11. Ernő Rubik,英文维基,https://en.wikipedia.org/wiki/Ern%C5%91_Rubik(生年、学历、应用艺术学院教职、二十七块木头的原型、1977 年匈牙利上市、1979 年授权 Ideal、1980 年全球发售;原型年份仍按文末说明处理) 12. Morwen Thistlethwaite 本人主页上的履历表,https://web.math.utk.edu/~mthistle/bio.html(1968–1972 曼彻斯特大学博士;1972–1975 Piano studies;1975–1978 北伦敦理工学院;1978–1987 伦敦南岸理工学院;2026 年 10 月 12 日读取);Morwen Thistlethwaite,英文维基,https://en.wikipedia.org/wiki/Morwen_Thistlethwaite(纽结理论;该页另说他学琴期间在伦敦开过演奏会,无脚注,履历表里没有,本文未采用);52 步的年份与上界见来源 1 的历史表(1981 年 7 月) 13. Optimal solutions for the Rubik’s Cube,英文维基,https://en.wikipedia.org/wiki/Optimal_solutions_for_the_Rubik%27s_Cube(科先巴把四段压成两段,此页作 1992 年,他本人的页面(来源 5)作 1991 到 1992 年;Cube Explorer 见来源 5 所在站点首页) 14. How to solve the Rubik’s Cube: Beginner’s Method,ruwix.com,https://ruwix.com/the-rubiks-cube/how-to-solve-the-rubiks-cube-beginners-method/(对照用:本文第三、四步的公式(右扳机、中层两条)与它的入门法相同;它的末层走另一条路,先摆棱、再摆角、最后用 R′ D′ R DR'\,D'\,R\,D 扭角,本文 v0.18–v0.23 曾按那条路写) 15. Rubik’s 3×3 Solve Guide,rubiks.com(Spin Master),https://rubiks.com/solve-guide,及随盒小册子 You Can Do The Rubik’s Cube Solution Guide(V1-EU-M-2020;V2-2020 同页同文)(§4 的八步分法、名字、顺序、各步持法和末层四条公式出自此:黄十字 p.28–29、黄面 p.30–31、黄角摆位 p.32–35、黄棱摆位 p.36–37;第三步白角的「扳机」说法和三种情形出自网页版 STEP 3,小册子 p.18–21 那一步是白十字朝上、用 DD 的另一组公式;公式字母串按小册子印的卡片逐字核过,本文每条都在程序里重算了它动哪些块) 10. 卢昌海《魔方与”上帝之数”》,《科学画报》2008 年第 12 期(鲁比克、科先巴、罗基奇三个译名的依据;辛马斯特一名按中文维基「魔方」条目的「大卫·辛马斯特」)

一处说明:一九七四年做出原型这件事,所有来源都是后来的转述,没有当年的一手件;文中凡涉及这个年份处,都按通行说法处理,不写成他本人的话。