一个3×3×3的魔方，看起来人畜无害——6个面、54个色块、6种颜色。但把它随便打乱十来下，你大概率就再也拧不回去了。而 Sebastian Lague，这位 YouTube 上最受程序员群体追捧的算法可视化博主之一，做了一个看似"耍赖"的决定：他不学怎么拧魔方，他要写一个程序，让电脑替他拧。
这听起来像偷懒，实际上是把自己扔进了计算机科学里最经典的战场之一——组合爆炸。这个视频《Coding Adventure: Solving the Rubik's Cube》之所以值得每个开发者看，不是因为它教你玩魔方，而是因为它用一只手就能转动的玩具，完整重演了一遍"算法工程师面对指数级问题时的全部挣扎与突围"：从天真地想用 BFS 广搜，到被状态空间按在地上摩擦，到引入启发式搜索、模式数据库，最后不得不向群论低头。
它解决的根本问题，其实是所有程序员都会反复遇到的那个——当问题规模大到搜索树塞不下内存，你该怎么办？ 魔方只是一个被美化到极致的教学案例。
| 项目 | 内容 |
|---|---|
| 视频标题 | Coding Adventure: Solving the Rubik's Cube |
| 频道 | Sebastian Lague |
| 时长 | 约 24 分钟（24:21） |
| 发布日期 | 2026年5月12日 |
| 频道订阅 | 140万+（1.4M） |
| 核心主题 | 用程序求解3×3魔方：状态表示、搜索算法与启发式 |
补充背景：该视频发布后不到一个月，Sebastian 又推出了续集《I Tried Optimizing my Rubik's Cube Solver》（2026年6月3日，27分钟），引入了 CFOP、Domino Reduction 等更激进的优化思路，在 Reddit 的 r/programming 板块引发了热烈讨论。本文以首集为分析主体，续集作为延伸。
视频的第一步，是让观众对"魔方到底有多大"建立一个物理直觉。一个魔方有多少种可能的打乱状态？答案是 43,252,003,274,489,856,000 种——约 4325亿亿（4.3×10¹⁹）。
这个数字怎么来的？魔方有 8 个角块（每个有 3 种朝向）、12 个棱块（每个有 2 种朝向），再加上整体朝向不算独立状态。组合数学给出：8 个角块的全排列 × 3⁸ 种朝向 × 12 个棱块的全排列 × 2¹² 种朝向，再除以 2（角和棱的奇偶性必须一致，否则物理上拼不出来）和 3（整体旋转不算），最终得到上面那个天文数字。
Sebastian 的洞察在于：这不是"难"，这是"大到没有边"。 如果你想用最笨的办法——把每种状态都存下来对比——就算你每秒存 100 万种状态，存完整个状态空间也需要 137 万年。这就是所谓的"组合爆炸"（combinatorial explosion）：问题的输入只是魔方上几十个色块，状态空间却是 10¹⁹ 量级。很多看似简单的题目，难度不在规则复杂，而在空间太大——这是视频埋下的第一颗认知钉子。
在动手搜索之前，Sebastian 必须先解决一个被新手严重低估的问题：怎么在代码里表示一个魔方？ 最直觉的做法是存 54 个色块的颜色——但这是个灾难，因为同一个魔方可以有很多种"颜色描述"（整体转一下，颜色变了，但其实是同一个状态）。
正确做法是把魔方拆成 20 个"小块"：8 个角块（corner cubies）+ 12 个棱块（edge cubies）。每个小块用它当前在哪个位置（permutation，排列）和它转到了什么朝向（orientation，朝向）来描述。这样，一个魔方状态就是一个"谁在哪个位、朝哪边"的紧凑编码。
【我的延伸分析】 这个选择为什么关键？因为搜索算法要反复做两件事：判断"两个状态是否相同"和"应用一步后变成什么"。用排列+朝向表示，"应用一步转动"就是一次排列变换（一个置换），可以用位运算或查表瞬间完成；"判断相同"就是比较两个排列向量。如果用颜色表示，这两步都会因为对称性而产生大量重复计算，搜索效率直接崩盘。数据结构的选择，在组合搜索里往往比算法本身更决定生死——这是我从这个视频里学到的最重要的一课。
Sebastian 在视频里（也是所有魔方求解器项目的必经之路）先尝试了最朴素的方法：广度优先搜索（BFS）。思路很直接——从当前状态出发，把所有可能的下一步都展开，逐层往外找，直到找到已解状态。
听起来合理，但魔方每个状态有 18 种合法转动（6 个面 × {90°顺、90°逆、180°}），BFS 层数与状态数的关系是指数级的：第 1 层 18 个状态，第 2 层约 324 个……到第 10 层附近，状态数已经突破千万。更致命的是，BFS 要把所有已访问状态存进内存做去重，而总状态数是 10¹⁹。内存会在第几层爆掉，几乎是注定的。
视频在这里传递的核心信息是：不是 BFS 错了，是问题配不上 BFS。 BFS 能保证找到最优解（最短转动序列），但它的内存代价是 O(b^d)，对于魔方这种分支因子 b=18、深度 d 最多 20 的问题，纯粹是"用错了工具"。这一步的价值在于建立对比——后面所有的高级技巧，本质上都是在回答"BFS 哪里不行，我们怎么补"。
这是整支视频最有诗意的知识点。God's Number（上帝之数）= 20，意思是：无论魔方被打乱成什么样，都一定能在 20 步以内（按半转计量 HTM，180°算一步）复原。20 就是这个上限，没有任何状态需要第 21 步。
这个结论不是猜的，是 2010 年由 Tomas Rokicki、Herbert Kociemba、Morley Davidson 和 John Dethridge 团队，借助 Google 提供的算力（约 35 个 CPU 年）正式证明的。1995 年，Michael Reid 就已经证明了一个叫 superflip（超级翻转）的状态恰好需要 20 步——所有块都在正确位置，但每个棱块都翻转了——它是已知的"最难"状态之一。在另一种计量方式 QTM（四分之一转计量，180°算两步）下，上帝之数是 26。
【我的延伸分析】 上帝之数 = 20 这个事实，对搜索算法的意义是颠覆性的：它告诉你最优解的搜索深度永远不超过 20。这把一个"无限深"的搜索问题，硬生生压缩成了"最多 20 层"的有界问题。BFS 失败不是因为它找不到（只要跑满 20 层，它一定能找到最优解），而是因为它要同时把 20 层的所有节点都放进内存。于是问题被重新定义为：如何在不把整棵树放进内存的前提下，找到深度 ≤ 20 的那条最优路径？ 这正是接下来 IDA* 登场的舞台。
主角登场。Sebastian（以及几乎所有现代魔方求解器）采用的算法是 IDA*（Iterative Deepening A，迭代加深 A*）。它是 A 的"内存友好版"。
A 用一个优先队列维护所有已发现的节点，按 f(n) = g(n) + h(n) 排序——g 是已走步数，h 是"估计还要走几步"的启发值。问题在于，A 要把整张搜索图都留在内存里，对魔方来说这就是 BFS 的内存噩梦。
IDA 的天才之处在于：它不存任何中间状态，每次只用深度优先（DFS）的方式往下走，并设一个"代价阈值"*。第一轮阈值设为 h(起点)，DFS 往下搜，只要某条路径的 g+h 超过阈值就剪枝；如果这一轮没找到解，就把阈值调大一点，重新从起点 DFS 一遍。反复迭代，直到找到解。
听起来很浪费——同一批浅层节点被反复访问很多次。但魔方搜索树的分支因子是 18，绝大多数节点都在最深层，浅层重复的开销可以忽略不计，而内存占用从 O(b^d) 降到了 O(d)，也就是只需一条从根到当前节点的路径。这是经典论文（Richard Korf, 1985）里"用时间换空间"的教科书级操作。IDA* 给了魔方求解一个既能找到最优解、又不会爆内存的可行框架。
IDA 好用，但它的效率完全取决于启发函数 h(n) 够不够准。如果 h(n) 永远是 0，IDA 就退化成纯 DFS，要在 18^20 里盲搜，照样跑不出来。所以整个魔方求解器的真正技术核心，是设计一个"又准又不算太慢"的 h(n)。
答案是 模式数据库（Pattern Database, PDB），由 Korf 在 1997 年的经典论文《Finding Optimal Solutions to Rubik's Cube Using Pattern Databases》中引入。思路极其优雅：提前只对魔方的一部分（比如 8 个角块）做一次完整 BFS，把"角块在每一种排列下需要几步复原"全部预存进一张表。运行时，把当前状态的角块部分抽出来查表，得到的数字就是一个"保证不超出实际所需步数"的估计——也就是一个可采纳的（admissible）启发值。
Sebastian 在视频里演示的，正是如何构建这种剪枝表/模式数据库。角块只有 8! × 3⁷ ≈ 8800 万种组合，预存得下；用同样的思路再为部分棱块建一张表，两个估计值取最大，h(n) 就变得相当锐利。搜索树的剪枝率因此飙升，原本 18^20 的巨树，被砍到可以在普通机器上几分钟甚至几秒内找到接近最优的解。 这是整个视频技术含量最高、也最值得反复琢磨的部分——它示范了"用预计算的存储，换取搜索时间的指数级下降"这一核心思想。
当模式数据库的内存也开始吃紧时，Sebastian（和他的续集）开始动用数学里更"降维"的武器——群论。这也是续集里提到 Domino Reduction（多米诺规约）和 r/programming 讨论中最兴奋的部分。
魔方本质是一个数学群（group）：所有合法转动构成群的"运算"，所有可达状态构成群的"元素"。两位先驱给出了两条著名的"分而治之"路线：
【我的延伸分析】 这一段最有教育意义的地方在于：它揭示了一个反直觉的工程策略——不要直接求解原问题，而是先把问题"约简"到一个更小、更结构化的子问题。 子群约束的本质，是牺牲一点点解的"最优性"，换取搜索空间数量级的坍缩。续集里 Sebastian 用 CFOP（速拧方法：Cross-F2L-OLL-PLL）和 Domino Reduction 做对比，本质上也是在权衡"解的步数"和"求解的速度"。一个 GitHub 上的同类项目描述恰好总结了这条心路："started with 'just use BFS' and ended with group theory, pruning tables"（从'就用 BFS 呗'开始，最后收场在群论和剪枝表）——这正是 Sebastian 视频的真实轨迹。
mindmap
root((用程序破解魔方))
敌人:状态空间
4325亿亿种状态
组合爆炸 b=18 d<=20
天真BFS必爆内存
基础:状态表示
20个cubie小块
排列permutation
朝向orientation
天花板:上帝之数
HTM下=20
QTM下=26
superflip最难态
内核:搜索算法
A星与优先队列
IDA星迭代加深
用时间换空间
内存O(b^d)降到O(d)
引擎:启发函数
模式数据库PDB
剪枝表pruning table
预计算换指数级剪枝
降维:群论
Thistlethwaite四阶段
Kociemba两阶段
子群规约Domino Reduction
延伸:速拧对比
CFOP方法
最优解 vs 求解速度
你大概率不会真的去写一个魔方求解器。但这个视频传授的思维模型，几乎可以平移到任何"搜索空间过大"的工程问题里。
第一，永远先量化"问题有多大"。 Sebastian 开篇就先把 4325亿亿这个数字摆出来，这不是炫技，而是工程纪律——在选择算法前，你必须先知道分支因子和最大深度。很多人写搜索/推荐/路径规划代码时一上来就 DFS，根本没估算过状态空间，结果上线后 OOM 崩溃。养成"先算 b 和 d"的习惯，能帮你在一开始就排除 90% 的错误方案。
第二，数据结构的选择先于算法。 视频里用"排列+朝向"而不是"颜色"来表示魔方，这一步决定了后面所有操作的效率。在你写任何递归/搜索逻辑前，先问自己：这个状态能不能用更紧凑、更易比较的方式编码？一个聪明的编码，往往顶得上一个更聪明的算法。
第三，掌握"用空间换时间、用时间换空间"的两种杠杆。 IDA* 是用时间换空间（牺牲浅层重复访问，换掉内存压力）；模式数据库是用空间换时间（预存子问题的解，换掉运行时的指数搜索）。成熟的工程师脑子里应该随时挂着这两根杠杆，遇到性能瓶颈时主动去拨动它。
第四，学会"约简"而不是"硬解"。 群论给魔方带来的启示是：与其在原始的巨大空间里硬搜，不如先定义一个中间目标，把问题缩小再缩小。这个模式在现实里到处都是——编译器先做语法分析再做优化、路径规划先做粗粒度图再做精细搜索、甚至你拆解一个庞大需求时先分层再细化，都是同一个思想。先问"能不能把问题变小"，再问"怎么在小问题上求解"。
第五，启发函数是启发式搜索的灵魂。 h(n) 的质量直接决定生死。任何用到 A/IDA/贪心搜索的场景（游戏 AI、地图导航、调度系统），你都应该花大量精力去设计一个可采纳且足够锐利的启发函数，而不是一味堆算力。模式数据库的思路——"把子问题预计算成一张表"——在很多领域都能复用。
这个视频最大的价值，是用一只手就能转动的魔方，把"如何用 IDA* + 模式数据库 + 群论，在一个 4325亿亿状态的空间里找到 ≤20 步的最优解"这件事讲透了——它其实是所有程序员面对指数级问题时的标准求生手册。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
fy0HRViXZnE，2026-05-12，24分钟，频道1.4M订阅达标），属于编程/算法领域，与全部历史轮次主题无重复。youtube_transcript.py fy0HRViXZnE 提取逐句字幕做精确引述（当前为基于权威资料的语义级还原）。[!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 等场景全覆盖。