# 穷举到宇宙尽头：魔方却永远20步可解 ## 导语 三阶魔方有多少种合法状态？答案是 **43,252,003,274,489,856,000**——约 4.3×10¹⁹，比宇宙大爆炸至今流过的秒数（约 4.35×10¹⁷ 秒）还多两个数量级。如果你试图用最笨的方法——从打乱状态一层层展开搜索树去穷举每一种走法——以每秒处理一百万个节点的速度，光是搜到第 20 层就要花掉大约一个宇宙年龄。可魔方真正反直觉的地方在于：**任何一种打乱，都一定能在 20 步以内还原**。这个被称为 "God's Number" 的数字，在 2010 年才被一群数学家用 Google 捐赠的 35 个 CPU 年最终坐实。 Sebastian Lague 的这期 *Coding Adventure: Rubik's Cube*，表面上是"写程序让电脑替我拧魔方"的玩具项目，骨子里却在演示一个所有程序员迟早要撞上的硬核命题：**当一个搜索空间大到连宇宙都装不下时，赢你的不是算力，而是你如何重新表述这个问题**。这期视频配上它的续集《I Tried Optimizing my Rubik's Cube Solver》，把从"贪心法"一路演进到"两阶段算法 + IDA* + 剪枝表"的完整工程弧线铺得明明白白。下面是我对它的深度拆解。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | Coding Adventure: Rubik's Cube | | 频道 | Sebastian Lague（订阅约 300 万+，单期常破百万播放） | | 时长 | 约 23 分 39 秒（续集约 26 分 11 秒） | | 播放量 | 百万级（Coding Adventure 系列常态） | | 核心主题 | 如何用状态编码 + 启发式搜索，让 4.3×10¹⁹ 的组合空间变得可解 | | 发布时间 | 2026 年 5 月（续集 2026 年 6 月） | | 源码 | GitHub: SebLague/Rubiks-Cube | ## 核心内容拆解 ### 1. 4.3×10¹⁹：一个让人本能想放弃的状态空间 魔方的状态数不是拍脑袋估的，是可以严格算出来的：8 个角块有 8! 种排列、3⁷ 种朝向（第 8 个被前 7 个决定），12 个棱块有 12!/2 种排列（奇偶性约束）、2¹¹ 种朝向。全部乘起来再除掉整体旋转冗余，就是那个 4.3×10¹⁹。 视频一开始就把这个数字摆出来，目的不是吓唬人，而是给后面所有设计定下基调：**你不能存它，也不能枚举它**。一个朴素的数组根本装不下这么多状态，任何"先把所有状态建好索引再查"的念头在第一步就破产。这逼着你换思路——不存全部状态，而是存"距离目标还有多远"的摘要。这是整个魔方求解算法体系的起点，也是 Lague 后面所有取舍的母题。 > 延伸提醒：这个"状态太大装不下"的处境，和数据库索引、游戏 AI、编译器寄存器分配、甚至大模型 KV cache 的处境是同构的——解法永远不是堆内存，而是找到一个能压缩状态的表示。 ### 2. God's Number = 20：答案小得离谱 4.3×10¹⁹ 这么大的空间，最深的状态离复原有多远？答案是 **20 步**（半步度量 HTM，把任意一面转 90°或 180°都算一步）。如果改用四分之一步度量（QTM，只把 90°算一步），上帝数字是 26。 这个结论来之不易。1981 年 Thistlethwaite 证明 52 步够用；1995 年 Michael Reid 证明 "superflip"（所有块位置正确、但所有棱被翻转）这个状态恰好需要 20 步，第一次把下界顶到 20；直到 **2010 年 7 月**，Rokicki、Kociemba、Davidson、Dethridge 才用 Google 捐赠的约 **35 CPU 年**算力，把上界也压到 20，彻底封口。 视频没有把 20 当冷知识一笔带过，而是用它制造一个戏剧张力：**空间无穷大，答案却短得能写在手心上**。这种反差直接指向核心问题——既然最优解不超过 20 步，为什么我们不能直接搜出它？答案在下一节。 ### 3. 为什么暴力 BFS 一定会死在沙滩上 直觉上，既然解最多 20 步，那从打乱状态做广度优先搜索（BFS），最多 20 层不就到了吗？问题出在**分支因子**。魔方第一步有 18 种走法（6 面 × 3 种转法），之后为了避免"转过去又转回来"的废步，每个节点的有效分支数约 13–15。 那么搜到第 20 层要展开多少节点？粗算 18 × 15¹⁹ ≈ **4×10²³** 个——这已经远超 4.3×10¹⁹ 的总状态数（因为搜索树里有大量重复路径）。按每秒处理一百万个节点算，4×10²³ ÷ 10⁶ ≈ 4×10¹⁷ 秒，约 **127 亿年**，差不多就是一个宇宙年龄。按每秒十亿个节点算，也要一千多万年。 所以暴力搜索不是"慢"，是"在物理上不可能"。这就是标题里"穷举到宇宙尽头"的来由——它不是夸张修辞，是字面意义上的算不出来。视频在这里完成了关键的认知转弯：**既然深搜撑不住，那就别深搜；把问题拆小，让每一层都只面对一个被压缩过的子空间**。 ### 4. 状态的编码方式决定求解器的生死 Lague 在视频里花了不少篇幅做一件看似无聊的事：**怎么用二进制位把魔方状态压到尽可能小**。角块朝向 3 种可以用 2 bit 存（浪费一点），棱块朝向 2 种用 1 bit，排列用排列索引编码……一个完整状态被压进几十个字节。 他反复强调一个工程观点：**你选什么表示，直接决定了你的求解器能跑多快、能塞进多少预计算表**。如果你用对象/数组松散地存每个块，做一次 move 要搬运一堆数据；如果你把状态压成一个整数坐标，move 就退化成查表（move table）。后面 Kociemba 算法之所以能在 1991 年那台 8MHz、1MB 内存的 Atari ST 上跑起来，靠的就是这一手：**把排列和朝向映射成自然数，把 move 实现成对这些数的查表**。 这一点对普通程序员极有启发：数据结构课上讲的"表示决定性能"，在魔方这种极端场景下被放大成生死线。同一个算法，换一种编码，速度差几个数量级。 ### 5. 从贪心到导向：三个 solver 与"启发式越强越难调"的权衡 视频原片对比了三种自建求解器： - **贪心求解器（greedy）**：每步选让评估函数最好的走法。简单、快，但容易钻进死胡同，解很长。 - **夹心求解器（sandwich）**：分层处理，先做一层再做中间。 - **导向求解器（oriented）**：优先把块"定向"到位。 Lague 的结论很务实：**启发式越强，实现越复杂，调参越痛苦**。最戳人的是一个藏在 22:32 的更正——他发现贪心评估器里偷偷给"朝向正确的角块"加了一点 bonus，这个看似无害的小分，会实质性地改变求解器的行为路径。换句话说，**一个常量级的打分调整，能在宏观上决定一个搜索算法走哪条路**。 这是启发式搜索最阴险的地方：它不报错、不崩，只是悄悄把结果带偏。所有写过游戏 AI、写过推荐排序的人都会对此会心一笑——你以为是算法的问题，其实是你三天前随手加的那个 `+0.1`。 ### 6. 真正的解法：把状态空间劈成两层 续集《I Tried Optimizing my Rubik's Cube Solver》才亮出真正的武器库：CFOP（人类速拧的 Cross/F2L/OLL/PLL）、domino reduction（多米诺约简）、迭代加深、IDA*、剪枝表、multi-search。这些技术最终都收敛向一个 1991 年由德国数学老师 Herbert Kociemba 提出的经典——**两阶段算法（Two-Phase Algorithm）**。 它的精髓是**用群论把巨大空间劈成两半**。魔方的所有合法操作构成一个群，其中有一个子群 G1 = ⟨U, D, R2, L2, F2, B2⟩（只允许上下两面任意转、其余四面只能转 180°）。这个子群里的状态有个漂亮性质：所有棱、角朝向都已归零，且中间层（UD-slice）的棱被锁在中间层。 于是求解被拆成两步： - **Phase 1**：把任意打乱状态拉进 G1（让所有朝向归零、中间层棱归位）。这一步最多 12 步。 - **Phase 2**：在 G1 内部，只用 ⟨U,D,R2,L2,F2,B2⟩ 这 6 个动作把魔方彻底复原。这一步最多 18 步。 第一次跑出来的解最多 30 步。但妙处在后头：算法不让 Phase 1 走"最短"，而是故意走一些**次优的 Phase 1 解**（比如多走一两步），再对每个次优 Phase 1 求 Phase 2 的最优——两者此消彼长，反复组合后，总步数通常压到 22 步以内，**经常能命中 20 步**。这就是"不追求单段最优、而追求整体最优"的工程智慧，和 Kociemba 在 Atari ST 上"几秒内出 22 步解"的历史对得上。 ### 7. 剪枝表 + IDA*：用预计算换搜索深度 两阶段本身只是把问题变小，真正让它"快"的是两件套：**剪枝表（pruning table）**和 **IDA\***（迭代加深 A*）。 剪枝表的核心思想是：**预先算好"从某个坐标到子目标至少还要几步"，存成查表**。搜索时，每展开一个节点，先查表——如果"已走步数 + 估计至少还差步数"已经超过当前允许的深度上限，整棵子树立刻砍掉，一个都不展开。这正是剪枝（pruning）的字面含义。 Kociemba 的实现里，Phase 1 用两张表（约各 6MB），Phase 2 用一张（约 22MB），总共约 35MB——一张表换来的，是把指数级搜索砍成几秒钟。再叠加**对称性约简**：魔方转个朝向不改变难度，24 种朝向 × 2 倍镜像 = 48 倍压缩，等价状态只算一次。 而 IDA* 是承载这套剪枝的搜索骨架：它像深度优先一样省内存（不像 A* 要存整个 open 表），又像广度优先一样能保证最优——通过不断抬高深度上限、每次从头深搜来实现。两者合体，就是"内存友好 + 剪枝激进 + 渐进最优"的黄金组合，也是几乎所有硬核组合优化求解器的标配。 ### 8. 最大的赢家不是算力，是剪枝 把两期视频连起来看，最值得带走的一句话不是某个公式，而是一条元规律：**当搜索空间爆炸时，最大的性能提升几乎永远来自更好的状态空间剪枝，而不是更快的代码或更强的机器**。 GameDev.net 对续集的点评一针见血："the biggest gains often come from better state-space pruning, not just faster code." 2010 年证明 God's Number 用的也不是蛮力，而是把 4.3×10¹⁹ 个状态切成 22 亿个 coset、再用对称性把要算的集合从 22 亿压到 5588 万，最后才用 35 CPU 年啃完——**砍掉 99.997% 的工作量靠的是数学，不是 GPU**。 这条规律迁移性极强：A* 寻路、AlphaBeta 剪枝、编译器常量折叠、SAT 求解器、数据库查询计划、甚至大模型推理的 KV cache 复用，本质都是同一件事——**与其让机器算更多，不如让问题本身更小**。 ## 知识结构图 ```mermaid flowchart TD A["打乱的魔方
状态空间 ≈ 4.3×10¹⁹"] --> B{能暴力 BFS 吗?} B --"分支因子≈15
深度20 ≈ 4×10²³ 节点
≈ 一个宇宙年龄"--> C["✗ 物理上不可行"] C --> D["Kociemba 两阶段分解
用群论劈开空间"] D --> E["Phase 1: 进入子群 G1
定向所有棱/角 + UD-slice 归位
≤12 步"] D --> F["Phase 2: 在 G1 内求解
只用 U,D,R2,L2,F2,B2
≤18 步"] E --> G["IDA* 迭代加深搜索
内存友好 + 渐进最优"] F --> G G --> H["剪枝表: 预算到子目标的最少步数
提前砍枝 (≈35MB 换指数级提速)"] H --> I["对称性压缩 48×
24 朝向 × 2 镜像"] I --> J["次优 Phase1 + 最优 Phase2
反复组合取整体最优"] J --> K["解 ≤20 步
= God's Number"] style C fill:#f4cccc style K fill:#d9ead3 ``` ## 实战启示 **如果你是算法/后端工程师**：这期视频是"状态空间搜索"最干净的教科书案例。下次遇到组合爆炸问题（排班、路径规划、配置选择、寄存器分配），别第一反应上暴力并行——先问三件事：能不能找一个**子目标**把问题分阶段（两阶段的本质）？能不能预计算一个**到目标的下界**做剪枝（剪枝表的本质）？能不能用**对称性**把等价状态合并？这三招任何一个落地，收益通常都比"加机器"大一个数量级。 **如果你做游戏 AI / 程序化生成**：Lague 在贪心评估器里那个 `+0.1` bonus 的教训值得刻在键盘上——启发式不会报错，只会悄悄带偏结果。上线任何评估函数前，做"消融实验"：把每个加分项单独关掉，看行为变化。一个小常量能决定整个 agent 的性格。 **如果你想自己动手**：从 GitHub 上拉 `SebLague/Rubiks-Cube` 源码读一遍，再对照 `kociemba.org` 的数学页和 `cube20.org` 的证明页。一个周末就能把"二进制状态编码 → move table → 剪枝表 → IDA*"这条链路亲手跑通，比读十篇论文都管用。 **认知升级**：记住这条心智模型——**算力解决线性问题，结构解决指数问题**。AI 时代大家习惯"大力出奇迹"，但凡是带"组合"二字的问题（而现实里大半难题都是组合问题），胜利永远属于会剪枝的人。 ## 延伸学习路径 1. **God's Number is 20**（cube20.org）——2010 年证明的原始站点，含完整历史表、最难状态、源码下载，是理解"20 步"来龙去脉的第一手资料。 2. **Kociemba 官方数学页**（kociemba.org/math/twophase.htm 与 imptwophase.htm）——两阶段算法作者亲笔，讲清 G1 子群、坐标映射、剪枝表构建，比任何二手解读都准。 3. **Sebastian Lague《I Tried Optimizing my Rubik's Cube Solver》**（续集）——把 CFOP、domino reduction、IDA*、剪枝表的演进过程可视化展示，是本文算法部分的视频正片。 4. **DeepWiki: Two-Phase Algorithm**（hkociemba/CubeExplorer）——基于 Cube Explorer 源码的自动文档，列出了 move table、pruning table 的精确尺寸和实现位置，适合想读代码的人。 5. **A* / IDA* 经典论文与实现**——把魔方当跳板，去理解通用的启发式搜索框架；推荐从 Reducible、Computerphile 的搜索算法视频入门，再读 Korf 的 IDA* 原始论文。 ## 一句话总结 面对 4.3×10¹⁹ 的状态空间，赢你的从来不是算力，而是**用群论把空间劈成两层、用剪枝表把指数砍成常数**——这套思路是所有组合优化问题的通用通关密码。 ## 参考来源 1. [Coding Adventure: Rubik's Cube — Sebastian Lague](https://www.youtube.com/watch?v=fy0HRViXZnE) — 本文分析的核心视频 2. [God's Number is 20 — cube20.org](http://www.cube20.org/) — God's Number 证明、35 CPU-years、状态距离分布表 3. [The Two-Phase Algorithm — Herbert Kociemba](https://kociemba.org/math/twophase.htm) — 两阶段算法原文（G1 子群、坐标、剪枝表） 4. [Two-Phase Algorithm Details — Kociemba](https://kociemba.org/math/imptwophase.htm) — 算法实现细节、Thistlethwaite 起源、对称性约简 5. [Coding Adventure: Rubik's Cube — GameDev.net 摘要](https://gamedev.net/news/3177/) — 视频内容结构化摘要（求解器对比、22:32 评估函数更正） 6. [I Tried Optimizing my Rubik's Cube Solver — Sebastian Lague](https://www.youtube.com/watch?v=Eysf6-E3ino) — 续集：CFOP / domino reduction / IDA* / 剪枝表 --- > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。