魔方算法背后的数学
一个 4.3×10¹⁹ 元素的群,和一场持续 30 年的追捕
本篇为综述,非译稿。事实与数字标注来源,归纳与判断为整理者解读。
先摆出那个让一切变得荒谬的数字:
约等于全球沙粒的量级。而答案是:任意一个局面,20 步之内必能还原。
一、为什么打乱了必然能还原?答案是「逆元」
知乎问题《在世界上还没有一个人成功还原魔方的时候如何证明魔方可还原》下,有个回答一句话点破:
你打乱的每一步倒着做,就一定能还原。在群论中,这叫必然存在可逆元素。
听起来像废话,但它是最深的那个起点。魔方的每一次转动都是集合上的一个置换,而置换都有逆置换。于是所有操作构成的集合满足封闭性、结合律、单位元、逆元——这就是魔方群。
更关键的是它不满足交换律(R U ≠ U R)。它是一个非交换群最日常、最具体的形象,比任何教科书例子都直观。
二、一个可以自己验证的现象,背后是拉格朗日
你随便拧一串动作,比如 R U R' U'(右手公式),然后一直重复。魔方会越来越乱,然后在某一刻突然回到原点。
知乎《对高中同学关于魔方重复步骤多次回到原点的答复》给的证明很干净:
固定步骤序列 在状态集上诱导了一个映射 。由于 有限, 的阶 必然存在,于是 。
换句话说:固定操作序列重复有限次,必然回到原点——不是巧合,是有限群元素的阶必然有限。
中国科普网《从魔方"上帝之数"到挂谷猜想》正是从这个小现象切入,把它当作「有限结构里的必然回归」的一个入口。
三、上帝之数:三十年追一个上下界
| 年份 | 人物 | 贡献 |
|---|---|---|
| 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。
这条路烧掉的算力,要分两段说清楚,别混成一次:
- 2008 年(上界压到 22 步):Tomas Rokicki 用的是电影特效商索尼影像(Sony Pictures Imageworks)——做过《蜘蛛侠》的那家——渲染农场的闲置算力,约 50 核年。
- 2010 年(最终证出 20 步):Rokicki、Kociemba、Davidson、Dethridge 通过对称性约简把总计算量压到约 35 CPU 年(约 10 亿 CPU 秒),实际跑在 Google 捐赠的服务器集群上。
一个玩具,先后用掉了一家好莱坞特效公司的空转时间和 Google 的机房。
四、superflip:既是「下界见证」,又在「群中心」
superflip 最反直觉的地方不是难,而是对称:
- 它是群的中心元素(center)——与所有操作可交换。魔方群的中心只有两个元素:单位元和 superflip。
- 它是阶为 2 的元素(做两次回到原点)。
- 它的角块完全归位,只有棱块翻转。
一个「最混乱」的局面,恰好是群论意义上「最中心」的元素。这个巧合在教学中特别有力量:混乱与对称,在群的结构里是同一件事的两面。
五、五类求解算法:都在「最优性 vs 速度」之间做取舍
| 算法 | 核心思路 | 耗时 | 步数 | 保证最优 | 典型用途 |
|---|---|---|---|---|---|
| 规则法(层先 / CFOP) | 人类流程写成 if-else + 查表 | 微秒级 | 50–100 | 否 | 教学、单片机玩具 |
| Thistlethwaite | 4 阶段群论子群降阶 | 毫秒级 | ≤45(平均 31) | 否 | 群论经典 |
| Kociemba 两阶段 | 降到 ,再在 内用 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(三个人名)。它不只解魔方,而是这类问题的通解:给定子群 的生成集,求 ;判断任意 是否属于 。
也就是说:魔方求解只是置换群算法的一道应用题。真正通用的成果是 Schreier-Sims,它同时服务于群阶计算、成员判定、轨道分解。魔方在这里是它的测试用例,不是目的。
七、最新一代:不用任何人类知识
2019 年,UCI 的 DeepCubeA 用逆向强化学习 + 加权 A* 解魔方:
- 不给任何人类公式、不给群论知识,纯从「如何从乱到整」反向学习
- 测试中 60.3% 的局面达到了最优步数,其余也接近最优
- 微软随后用异步 MCTS + 策略/价值网络做了类似工作
方法论上有意思的地方是:深度学习最怕「稀疏奖励」,而魔方恰恰是「走错一步看不出坏在哪里」的典型。所以这里的突破不在模型规模,而在如何定义中间目标。
八、给工程的三点迁移
- 有限且可逆,就一定可解:只要操作可逆、状态有限,就存在回路。遇到「看起来无解」的系统,先问「状态集有限吗、操作可逆吗」。
- 降维比暴力强:4.3×10¹⁹ 个状态,BFS 到第 9 步就爆内存。而 Kociemba 一个子群约束就把搜索空间砍掉几个数量级。好的约束比好的硬件值钱。
- 真最优往往不值:Korf 用小时换「绝对最优」,Kociemba 用毫秒换「够好」。产品里 99% 的场景该选后者。
- 中心与混乱是一回事: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。
修订说明 本文修订了初版两处问题:① 把 2008 年(Sony Pictures Imageworks,上界 22 步,约 50 核年)与 2010 年(Google 捐赠集群,最终证出 20 步,约 35 CPU 年)的算力来源混为一谈;② 第五节标题「四代」与表格中五类算法不一致,已改为「五类」。初版链接为 /post/1795076173567,以本版为准。