魔方复原教程及快速解法3D演示
你的程序里其实用到了两套思路完全不同的“复原策略”:
- 「教程演示」:面向人类的层先法(LBL),分七步由底到顶逐层复原(好记,但通常要 70~100 多步)。
- 「填色求解」:面向计算机的 Kociemba 两阶段算法(Two-Phase Algorithm),通过你内嵌的
cubejs库在本地运行。
下面重点讲清楚这套核心求解算法。
一、你的求解器用的什么算法?怎么工作的?
魔方一共有约 (4300 亿亿) 个合法状态。如果直接用广度优先搜索暴力穷举,全世界的内存加起来都不够装。
Kociemba 算法的核心思想是借助数学里的“群论”分两步降维,对应你代码 solve.js 里的 phase1 和 phase2:
第一阶段(Phase 1):把魔方赶进“特殊子群 ”
这一步允许全部 18 种转动(上下左右前后 6 个面,每面顺时针 90°、180°、逆时针 90°),但目标不是还原颜色,而是把魔方“整理”成一种极其规整的中间状态 。
只要满足下面 3 个条件,魔方就进入了 (对应 solve.js 里的三个坐标):
- 8 个角块朝向正确(
twist,共 种状态); - 12 个棱块朝向正确(
flip,共 种状态); - 中层(赤道圈)的 4 条棱块都回到了中层位置(
slice/FRtoBR,共 种状态)。
把原本 的庞大空间,一下子压缩成了几千级别的“坐标查表”问题。
第二阶段(Phase 2):在 内部直接复原
一旦进入 ,算法就禁用侧面(前/后/左/右)的 90° 转动,只允许使用 10 种操作(对应代码里的 allMoves2):
- 顶面
U, U2, U'、底面D, D2, D' - 前后左右只能转 180°:
R2, L2, F2, B2
这 10 种操作有一个神奇的数学性质:它们永远不会破坏第一阶段调好的角/棱朝向,也不会把中层棱块甩出去。所以第二阶段只需要用 URFtoDLF(角块位置)、URtoDF(上下层棱块位置)、FRtoBR(中层棱块顺序)和奇偶性 parity 查表,把位置归位就彻底还原了。
怎么搜得这么快?——「剪枝表 + IDA*」
你在程序里点第一次「求解」时会花 1~2 秒初始化,就是在生成 Move Tables(状态转移表) 和 Pruning Tables(剪枝距离表,如 sliceTwist、sliceFlip 等)。之后每次搜索采用 IDA(迭代加深 A)**:每走一步就查表估算“至少还要几步才能到终点”(minDist1、minDist2),一旦发现剩余允许步数不够,立刻剪枝回头,所以能在毫秒到零点几秒内搜出解。
二、发明人是谁?
这套算法的发明人是 Herbert Kociemba(赫伯特·科琴巴),德国达姆施塔特的一位数学老师兼计算机魔方研究者。
他的研究有三个非常传奇的里程碑:
- 1991–1992 年提出两阶段算法:他受到英国数学家 Morwen Thistlethwaite(1981 年提出四阶段算法,最多 52 步)的启发,在一台只有 8 MHz CPU、1 MB 内存的 Atari ST 老式电脑上,把四个中间群强行浓缩成两阶段,并写了著名的开源魔方程序 Cube Explorer。
- 2010 年参与证明“上帝之数 = 20”:Kociemba 与 Tomas Rokicki、Morley Davidson、John Dethridge 组成四人团队(利用 Google 捐赠的约 35 个 CPU-年的空闲算力),基于两阶段算法的陪集划分思想,彻底证明了:任意打乱的三阶魔方,在半圈度量(180° 算 1 步)下最多只需要 20 步就能复原。
- 你代码里的
cubejs:是开发者 Petri Lehtinen 将 Kociemba 公开的 Java 简化参考版(不带对称性压缩)移植到 JavaScript 的开源库。
三、这套算法靠谱吗?
非常靠谱——它是过去 30 多年里计算机解三阶魔方的事实工业标准。 世界上绝大多数魔方机器人、WCA 官方打乱生成器、主流在线魔方求解器底层用的都是它。
不过客观来看,它在你的程序里也有几个特性和边界需要注意:
- 步数短,但追求的是“接近最优”而非“绝对最少步”
- Kociemba 完整版(如 Cube Explorer)在找到第一个解之后会继续搜更短的路径,平均能压到 18~20 步以内。
- 而你用的
cubejs默认设定了maxDepth = 22,并且只要找到第一个总长度 步的解就立刻停止并返回(if (solution !== null) break;)。这对你的教学/求解软件是极其合理的设计:牺牲一点点极致步数(依然只有 18~22 步,比层先法的 80+ 步短太多),换来在浏览器 JS 环境下亚秒级的实时响应。
- 速度与内存极其适合浏览器
- 原版高速 Kociemba 会用对称性约简生成几十上百 MB 的大表,不适合放进单文件网页;
cubejs放弃了对称性约简,只保留几张核心小表,换来了整个单文件 HTML 只有几百 KB、无需联网就能本地秒解的体验。
- 原版高速 Kociemba 会用对称性约简生成几十上百 MB 的大表,不适合放进单文件网页;
- 本身对“非法输入”很脆弱——但你的程序补齐了这个短板
- 这是原生
cubejs唯一“不靠谱”的地方:它默认传入的 54 格魔方一定能还原,如果用户不小心涂错了一格,Cube.fromString(fl).solve()不会友好提示,反而可能吐出一串莫名其妙的假步骤或直接报错。 - 不过你自己在外部加上了非常严密的
diagnoseFacelets()物理前置校验(检查颜色总数、合法角/棱组合、重复块、角块扭转总和% 3、棱块翻转总和% 2、角棱置换奇偶性),还有try/catch兜底,把原生库唯一的短板也彻底堵住了。
- 这是原生
总结:原理上经过了“上帝之数”数学证明的背书,工程上又有你的前置物理校验兜底,这套算法在你的程序里是非常靠谱且精准的选型。