魔方算法背后的数学:一个 4.3×10¹⁹ 元素的群

魔方算法背后的数学

一个 4.3×10¹⁹ 元素的群,和一场持续 30 年的追捕

本篇为综述,非译稿。事实与数字标注来源,归纳与判断为整理者解读。


先摆出那个让一切变得荒谬的数字:

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

约等于全球沙粒的量级。而答案是:任意一个局面,20 步之内必能还原。

一、为什么打乱了必然能还原?答案是「逆元」

知乎问题《在世界上还没有一个人成功还原魔方的时候如何证明魔方可还原》下,有个回答一句话点破:

你打乱的每一步倒着做,就一定能还原。在群论中,这叫必然存在可逆元素。

听起来像废话,但它是最深的那个起点。魔方的每一次转动都是集合上的一个置换,而置换都有逆置换。于是所有操作构成的集合满足封闭性、结合律、单位元、逆元——这就是魔方群。

更关键的是它不满足交换律(R U ≠ U R)。它是一个非交换群最日常、最具体的形象,比任何教科书例子都直观。

二、一个可以自己验证的现象,背后是拉格朗日

你随便拧一串动作,比如 R U R' U'(右手公式),然后一直重复。魔方会越来越乱,然后在某一刻突然回到原点。

知乎《对高中同学关于魔方重复步骤多次回到原点的答复》给的证明很干净:

固定步骤序列 WW 在状态集上诱导了一个映射 f∈Sym⁡(S)f \in \operatorname{Sym}(S)。由于 ∣S∣=N|S| = N 有限,ff 的阶 kk 必然存在,于是 fk=ef^k = e。

换句话说:固定操作序列重复有限次,必然回到原点——不是巧合,是有限群元素的阶必然有限。

中国科普网《从魔方"上帝之数"到挂谷猜想》正是从这个小现象切入,把它当作「有限结构里的必然回归」的一个入口。

三、上帝之数:三十年追一个上下界

年份 人物 贡献
1981 Thistlethwaite 上界压到 52 步
1992 Kociemba 两阶段算法,实际求解 20 步左右
1995 Michael Reid 上限降到 29;同时证明 superflip 至少需要 20 步,把下界钉死
2010 Rokicki / Kociemba / Davidson / Dethridge 上界降到 20,上帝之数确定为 20

关键在于 1995 年那一步。Reid 找到了一个候选局面——12 个棱块全部翻转、角块和位置都对,也就是 superflip(中文多译「超翻转」)。它至少需要 20 步。

于是上下界合围:上界 29,下界 20。剩下的工作,是把上界从 29 砍到 20。

2010 年那次证明烧了多少算力?一个有画面感的细节:

罗基奇的计算得到了电影特效商**索尼影像(Sony Pictures Imageworks)**的支持,这家曾为《蜘蛛侠》做特效的公司提供了相当于 50 年不停歇计算的资源。

总计约 35 CPU 年。一个玩具,用掉了一家好莱坞特效公司的机房。

四、superflip:既是「下界见证」,又在「群中心」

superflip 最反直觉的地方不是难,而是对称:

  • 它是群的中心元素(center)——与所有操作可交换。魔方群的中心只有两个元素:单位元和 superflip。
  • 它是阶为 2 的元素(做两次回到原点)。
  • 它的角块完全归位,只有棱块翻转。

一个「最混乱」的局面,恰好是群论意义上「最中心」的元素。这个巧合在教学中特别有力量:混乱与对称,在群的结构里是同一件事的两面。

五、四代求解算法:都在「最优性 vs 速度」之间做取舍

算法 核心思路 耗时 步数 保证最优 典型用途
规则法(层先 / CFOP) 人类流程写成 if-else + 查表 微秒级 50–100 否 教学、单片机玩具
Thistlethwaite 4 阶段群论子群降阶 毫秒级 ≤45(平均 31) 否 群论经典
Kociemba 两阶段 降到 G1=⟨U,D,L2,R2,F2,B2⟩G_1=\langle U,D,L^2,R^2,F^2,B^2\rangle,再在 G1G_1 内用 IDA* 毫秒级 18–21 渐近最优 工程首选
Korf IDA* + 模式数据库(PDB) 秒到分钟 ≤20 是 求绝对最优
DeepCubeA 逆向强化学习 + 加权 A* 秒级(需算力) ~20(60.3% 最优) 近似最优 通用组合优化研究

三个反直觉的点

① 最优解,反而最慢。

Korf 1997 年用模式数据库做到了「绝对最优」,代价是解一个随机局面要数小时。Kociemba 毫秒出解,但不保证最优。

工程上从来不用「真最优」——这句话在魔方这里体现得最彻底。

② 两阶段各自最优,合起来未必最优。

知乎《魔方还原算法二——科先巴的二阶段算法》讲得清楚:

阶段二的最优是相对于阶段一而言的。两个阶段都各自最优,合起来明显不是最短路径。

解决办法是加深第一阶段的搜索深度——让第一阶段故意走长一点,为第二阶段换更短的尾部。这是「局部最优不等于全局最优」最朴素的实例。

③ 上帝之数 20,但绝大多数局面用不到 20 步。

距离分布高度集中在 18 步附近,需要 20 步的只是极少数(含 superflip 那类)。「20」是一个最坏情况的上界,不是平均难度。

六、被低估的那个算法:Schreier-Sims

知乎《如何利用群论的知识解决三阶魔方》提到一个常被忽略的名字:

降群法,真名叫 Schreier-Sims(三个人名)。它不只解魔方,而是这类问题的通解:给定子群 G≤SnG \le S_n 的生成集,求 ∣G∣|G|;判断任意 gg 是否属于 GG。

也就是说:魔方求解只是置换群算法的一道应用题。真正通用的成果是 Schreier-Sims,它同时服务于群阶计算、成员判定、轨道分解。魔方在这里是它的测试用例,不是目的。

七、最新一代:不用任何人类知识

2019 年,UCI 的 DeepCubeA 用逆向强化学习 + 加权 A* 解魔方:

  • 不给任何人类公式、不给群论知识,纯从「如何从乱到整」反向学习
  • 测试中 60.3% 的局面达到了最优步数,其余也接近最优
  • 微软随后用异步 MCTS + 策略/价值网络做了类似工作

方法论上有意思的地方是:深度学习最怕「稀疏奖励」,而魔方恰恰是「走错一步看不出坏在哪里」的典型。所以这里的突破不在模型规模,而在如何定义中间目标。

八、给工程的三点迁移

  1. 有限且可逆,就一定可解:只要操作可逆、状态有限,就存在回路。遇到「看起来无解」的系统,先问「状态集有限吗、操作可逆吗」。
  2. 降维比暴力强:4.3×10¹⁹ 个状态,BFS 到第 9 步就爆内存。而 Kociemba 一个子群约束就把搜索空间砍掉几个数量级。好的约束比好的硬件值钱。
  3. 真最优往往不值:Korf 用小时换「绝对最优」,Kociemba 用毫秒换「够好」。产品里 99% 的场景该选后者。
  4. 中心与混乱是一回事:superflip 既是「最乱」,又在群中心。判断一个系统的复杂度,不能只看表面熵。

来源

  • 知乎:猫羽雫(重复步骤回原点)、叶精灵(可还原性证明)、ClefRybak(上帝之数史)、ACE(Schreier-Sims / 降群法)、Rand(Kociemba 两阶段)、陈霜(上帝之数 / N 阶魔方)、量子位(MCTS 魔方)
  • 腾讯元宝检索:CubeRoot 系列(魔方群结构、著名图案、上帝之数 20)、Math StackExchange(Center of the Rubik's Cube Group)、Korf《Finding Optimal Solutions to Rubik's Cube Using Pattern Databases》(AAAI 1997)、DeepCubeA 报道(UCI / ScienceDaily)、中国科普网《从魔方"上帝之数"到挂谷猜想》

数字与结论以上述来源为准,未独立复核原始论文;归纳与判断为整理者解读。


整理于 2026-11-19。