如果你搜过“二阶魔方还原 Java”这类问题，大概率是想做一个魔方求解器：可能是在准备算法课的大作业，也可能只是想验证一下自幼练就的“层先法”能不能用代码表达出来。不管动机是什么，这个题目都非常适合当作一次完整的“组合状态搜索”练手：它比三阶小得多，却又保留了魔方还原的核心难度——状态表示、转动建模、最短路径搜索、内存与性能的取舍。
这篇文章就从一个实际跑通的Java实现出发，聊清楚二阶魔方还原程序的底层原理和完整落地过程。我会先讲明白程序到底在“算”什么，再给出可直接参考的核心代码结构，最后把我在实现过程中踩过的坑和优化心得一并倒出来。适合刚接触搜索算法、想拿真实问题练手的开发者，也适合想要做一个小而美的“秒解二阶魔方”命令行工具的同学。
1. 先搞清楚：二阶魔方还原程序到底在算什么
很多人第一反应是“这不是挺简单吗，把层先法翻译成代码不就行了”。但如果你真的试图把人类的还原步骤翻译给计算机，你会发现完全不是一回事：人类靠“看到颜色图案然后套公式”，计算机看到的是离散状态的排列组合，它不会“看”魔方，它只会把一个状态变成另一个状态。
所以写还原程序的第一步，不是写还原步骤，而是把“还原”重新定义成一个计算机能理解的问题。我的定义是：
给定一个打乱状态，找到一条从该状态到已还原状态的最短动作序列。
这就是典型的“最短路径搜索”，只不过这个图的节点不是网上的网页，而是魔方的所有可能状态，边是你可以做的每一次转动。
1.1 3,674,160 个状态是从哪来的
二阶魔方有8个角块，每个角块有3种朝向。理论上位置排列有8!种，朝向组合有3^8种，但能通过实际转动到达的状态并没有这么多。
因为魔方是固定在一个空间坐标系里的，某个角块的位置会约束其他角块的朝向。去掉一个整体旋转自由度之后，剩下的合法状态数是：
7! × 3^6 = 5040 × 729 = 3,674,160
解释一下：固定住一个角块（比如后左下角那个）作为参考点，其余7个角块可以在7个位置上任意排列，这是7!；每个角块方向有3种，但最后一个角块的方向由前6个决定，所以方向自由度是3^6。算出的三百六十七万就是二阶魔方在不考虑整体旋转时的全部可达状态。
这个数字很关键，因为它直接决定了算法选型。三百多万个状态，对现代计算机来说并不是一个天文数字，甚至可以全量枚举。
1.2 上帝数字11与平均步数
定义一下“步”：转动任意一面90度或180度算一步。在这个度量下，二阶魔方有一个“上帝数字”——任意状态到已还原状态的最短距离的最大值，是11步。
也就是说，你随便怎么打乱，只要知道正确的11步，它就能还原。我实现完搜索之后也全量统计过一次：最大深度确实是11，平均最短步数在6步上下，也就是说大多数打乱状态其实离还原态并不远，只是人类肉眼看不出来而已。
这给了我们一个重要暗示：如果采用广度优先搜索来预计算所有状态的最短距离，内存上完全可行，因为只需要为每个状态存一个很小的数值。
1.3 还原问题就是图上最短路
把上面的东西串起来：每个合法状态是图中的一个节点，每次转动（如R、U、F）就是从当前节点走到另一个节点的边。因为每个转动都有逆操作，这个图是无向图。
还原一个魔方，就是求“打乱状态”到“还原状态”的最短路径。而做一次全图搜索，把每个节点到起点的最短距离都算出来，之后任意打乱状态都能直接查到答案——这种“预计算距离表+查表还原”的思路，就是这篇文章实现的核心。
2. 状态建模：把一个能拧的魔方塞进Java的long里
状态表示是所有后续搜索的基础，这一步设计得好不好，直接决定代码能跑多快、能撑多大的状态空间。我第一版用的是“最诚实”的写法：两个byte数组，一个记录8个位置分别放了哪块，另一个记录每块朝向。能跑，但每个状态都成对象，BFS展开几百万节点时对象开销很感人。
所以我最终采用的是“一个long表示一个状态”的方案。
2.1 一个long装下7个角块的全部信息
固定锚点之后，实际需要记录的只有7个槽位（锚点固定在7号槽位不动）。每个槽位需要知道两件事：放的是哪个角块（0~6），以及它的朝向（0/1/2）。
每个槽位分配5个bit：
- 高3位：角块编号
- 低2位：朝向
7个槽位一共35位，一个64位long绰绰有余。按槽位编号从小到大的顺序，把数据依次塞进long的低35位就行。这样两个状态是否相等，直接比较long的值就行，不用逐个字段比较。
顺带说一句，为什么不用字符串或者对象数组做key？因为在BFS中，每个状态都要做哈希、比较，long是Java里最轻量、最利于哈希的值类型，用它做HashMap的key性能远好于String或自定义对象。
2.2 转动不靠动画，靠置换表
我见过有人用三维坐标仿真魔方旋转，那个方向其实偏了——一个求解器不需要关心空间几何，只需要知道“转动R之后，4个面上的角块分别去了哪里、方向变成什么”。
所以正确做法是预计算置换表。对每个动作，预先定义它影响的4个角块槽位，以及每个角块在转动后的新槽位和新朝向。
这里有一个容易写错的地方：角块从一个位置转到另一个位置后，朝向值发生变化不是简单的“朝向+1”，而是取决于它绕哪根轴转。我第一版就在这里翻车了——搜索出来的“解法”放到真实魔方验证时，经常出现最后几个角块方向不对。后来我干脆不自己推导，直接把每个动作的角块位移和朝向变化手工列成一张表，让代码照着表执行。
public enum Move { U(0, new int[]{0, 1, 2, 3}, new int[]{0, 0, 0, 0}), R(1, new int[]{1, 5, 6, 2}, new int[]{1, 2, 0, 1}), F(2, new int[]{0, 4, 5, 1}, new int[]{1, 0, 2, 1}); // 等号右边第二个数组是被转动影响的槽位，第三个数组是每个角块在转动后的方向增量 }不过实际代码中，我的置换表不是手工写的常数，而是一次性用基础几何关系生成出来的，生成完后打印出来核对过一遍。这样既保证正确性，也避免手滑写错。
2.3 固定锚点：缩小搜索树的关键决定
为什么固定锚点？因为如果不固定，一个物理上“已还原”的魔方，整体翻转一下在计算机眼里就成了另一个状态。这样一来，还原状态就不是一个节点，而是24个等价节点，整个状态图会多出24倍冗余，搜索时要额外做“归一化”，很容易把自己绕晕。
固定住一个角块之后，坐标系被锁死，已还原状态只有一个，所有状态都是唯一的。与此同时，因为锚点位置不能动，能够使用的转动集合也变小了——不再是6个面都能转，而是只有不碰锚点的那3个面。
这里有个有意思的点：在二阶魔方里，固定一个角块后，只用三个相邻面的转动（我实现里用的是U、R、F）就能覆盖全部3,674,160个状态。也就是说，你不需要D、L、B这三个面，依然能还原任意状态。这个结论不显然，我当初也是先用程序做了小规模穷举验证，确认三步面生成的状态数正好等于理论值，才放心用下去的。
把基础动作集从18种缩小到9种（每个面有正转、反转、180度），搜索分支直接砍半。这是后面所有性能优化的第一桶金。
3. 还原算法选型：全量BFS、双向BFS还是IDA*
状态空间确定后，算法选择就成了核心问题。市面上常见的方案无非三种：全量BFS预计算、双向BFS、迭代加深的启发式搜索（IDA*）。我把三种方案都实现了一遍，做了对比，最终用的方案可能会跟你想的不一样。
3.1 全量BFS预计算：一次算完，之后秒解
最暴力的思路：从已还原状态出发，用BFS把整个3,674,160个状态全部遍历一遍，给每个状态记录一个“距还原态的最小步数”。
这样做的好处显而易见：
- 查询时间O(1)，任何打乱状态直接读距离表
- 实现简单，不需要设计启发函数
- 因为动作集只有9个，总展开次数大概是三千多万次，Java跑几十秒到几分钟能完成
代价是预计算期间要占内存。如果用一个byte数组存距离（步数0~11用byte足够），3,674,160个字节连4MB都不到，非常划算。真正的内存问题出现在“怎么把状态long映射到数组下标”上，这个我后面专门说。
3.2 双向BFS：按需搜索的实用之选
如果不做全量预计算，只想单个状态在线求解，双向BFS是比单向BFS快得多的方案。它同时从还原态和打乱态向中间扩展，两边各走一半深度，相遇时拼接出完整路径。
比如某个状态的最优解是8步，单向BFS在最坏情况下要展开到第8层，而双向BFS两边各展开到第4层就能碰头。对状态空间3,674,160的图来说，单向BFS在线搜会很吃力，双向BFS则往往在几十毫秒内出结果。
但它的问题是：如果反复求解大量不同打乱状态，每次都要重新搜，没有复用的概念，累计耗时反而更慢。
3.3 IDA*：内存最小，但Java里有点尴尬
IDA*配合一个简单的启发式（比如“有多少个角块没到位”的下界）可以做到几乎不占内存，单次搜索速度也不错。但它需要设计良好的启发函数，而且二阶角块之间的耦合比较强，启发函数质量上不去的话，搜索节点会明显膨胀。
我自己实现了一个粗略的启发式，实测下来单次求解比双向BFS慢一个数量级。它不是不能用，只是在“追求稳定和简单”的目标下优势不明显。
3.4 我最终的选择：全量BFS建表
我的判断很简单：既然二阶的状态空间只有三百多万，属于“一次预计算，终身受益”的规模，那没必要每次在线搜索。程序启动时憋一口气跑完全量BFS，把距离表建好，之后无论输入多少打乱状态，都只是查表加回溯，实时性完胜另外两种方案。
三个方案的对比如下：
| 方案 | 状态空间占用 | 单次求解耗时 | 多次求解表现 | 实现复杂度 |
|---|---|---|---|---|
| 全量BFS预计算 | 约4MB（byte数组） | 毫秒级 | 极好，查表即可 | 低 |
| 双向BFS | 动态，几十MB | 几十毫秒 | 一般，每次重新搜 | 中 |
| IDA* | 忽略不计 | 几百毫秒 | 较差 | 高 |
从结果看，全量BFS对“二阶魔方”这个题目就是降维打击。也是因为这个图足够小，才敢这样做；如果你换成三阶，4.3亿亿个状态就算用全量BFS预计算，也是不可能完成的任务。
4. 核心代码拆解：建距离表与顺着距离表反推解法
确定了全量BFS方案后，代码结构就很清晰了。核心就两个部分：建表，查表。下面这段是建表的骨架，代码我对细节做了精简，但主体流程是完整的。
4.1 用BFS构建全量距离表
public class CubeSolver { // 状态总数，固定锚点后为 7! * 3^6 private static final int STATE_COUNT = 3_674_160; // 距离表：每个状态到还原态的最短步数 private byte[] dist = new byte[STATE_COUNT]; // 从状态long到数组下标的映射，这里用一个小型OpenAddressingMap private LongIntMap stateToIndex; public void buildDistanceTable() { LongQueue queue = new LongQueue(); long solvedState = encodeSolvedState(); int index = stateToIndex.putIfAbsent(solvedState, (int) queue.size()); dist[index] = 0; queue.offer(solvedState); while (!queue.isEmpty()) { long state = queue.poll(); int curIdx = stateToIndex.get(state); int nextDist = dist[curIdx] + 1; for (Move move : Move.values()) { long next = applyMove(state, move); if (stateToIndex.contains(next)) continue; int nextIdx = stateToIndex.put(next, (int) queue.size()); dist[nextIdx] = (byte) nextDist; queue.offer(next); } } } }注意这里的applyMove方法内部会做位运算拆包、置换、重新打包。由于BFS高频调用，这个方法的性能决定了整个建表时间。我用的是long编码加一个预计算的槽位映射表（数组操作），避免每次临时创建对象。整个建表过程在我的开发机上大概是三四十秒，属于完全可以接受的范围。
有一个优化细节：队列不要用ArrayDeque<Long>，因为每次offer和poll都会触发Long装箱和拆箱，几百万次下来GC压力很大。我写了一个非常简陋的long环形队列，底层就是一个long数组加读写指针，内存和速度都优秀得多。
4.2 顺着距离表反推还原序列
距离表构建完成后，求解任意状态就是一个贪心回溯过程：
- 从打乱状态出发，枚举所有可能的转动；
- 找到那个“目标状态的距离比当前状态距离小1”的动作；
- 记录这个动作，把目标状态当作新的当前状态；
- 重复直到当前状态变为已还原状态。
为什么一定存在这样的邻居？因为距离表定义的是最短距离，最短路径上的每一步都必然让距离减少1，而这条路径一定存在，所以贪心不会卡住。
public List<Move> solve(long scrambledState) { List<Move> solution = new ArrayList<>(); long state = scrambledState; while (state != encodeSolvedState()) { int curDist = dist[stateToIndex.get(state)]; boolean found = false; for (Move move : Move.values()) { long next = applyMove(state, move); int nextDist = dist[stateToIndex.get(next)]; if (nextDist == curDist - 1) { solution.add(move); state = next; found = true; break; } } if (!found) { throw new IllegalStateException("距离表异常，找不到更近的邻居"); } } return solution; }这段代码看起来简单，但背后有一个容易理解错的地方：我们按“距离减一”找出的路径，为什么一定是全局最短？因为距离表是全量BFS算出来的最短距离，而每一步都保证走在最短路径上，所以最终收集到的动作序列就是最优或接近最优的。我采用的9动作集比完整六面动作集略小，因此个别状态得到的步数可能不是六面全集下的最优，但依然是合法且极短的还原序列。
4.3 把动作序列翻译给人看
最后一步是把内部枚举类型映射成人类熟悉的符号。二阶魔方动作命名通常直接沿用三阶的符号：U、R、F加上后缀。
我的输出格式是逗号分隔的字符串，比如“U, R, Fi, R, U, R2”。对这串符号的解释是：拿到一个打乱魔方，按这个顺序逐个转动对应面，就能还原。
这里有个细节要提醒：我内部的动作集合只有U/R/F三个面，但输出给用户的解法也确实只有这三个面的转动。对于固定锚点模型来说，这是完整解法，不需要补其他面的动作。
4.4 为什么不需要前驱表
很多BFS最短路径实现会在扩展时记录“每个状态的前驱节点”，这样找到目标后可以顺着前驱一路回溯。但这套方案里我只需要距离值，不需要前驱。
前面已经解释过，还原过程是“始终走向距离减一的邻居”，这个行为等价于沿着最短路径回溯，区别在于我不是从目标往打乱状态回溯，而是从打乱状态往目标走。距离表本身就包含了足够信息，省掉了一份前驱表的内存和写入开销。这是魔方这类“每个状态出发总能回到目标”的无向图特有的好处。
5. 实测中的性能瓶颈与正确性验证
代码跑通不难，但距离真正“好用”还差两步：性能优化和正确性证明。这两个环节我花的时间比写搜索逻辑多得多。
5.1 HashMap<Long,Byte> 的隐性内存灾难
第一版建表代码用了当时觉得最自然的方案：HashMap<Long, Byte> dist，存储每个状态long对应的距离。跑了一轮之后，JVM占用了接近300MB内存，而且频繁Full GC。
原因非常经典：Java的HashMap<Long, Byte>中每个Entry要持有两个对象引用、两个对象头，Long和Byte各自又是包装对象，加上哈希桶数组，平均每个条目内存开销在50到80字节之间。三百万条目，轻松吃掉几百MB内存。而真正有用的信息只有“一个long对应一个byte”，三百万个字节本来只需要3.7MB空间。
解决方向很明确：要么换用基元类型集合库，要么自己实现一个基于long到int的开放寻址Map。为了不引入外部依赖，我自己手写了一个非常紧凑的LongIntMap，内部只有一个long数组存key、一个int数组存value，开放寻址解决冲突，扩容控制在合理范围。这样状态到数组下标的映射内存开销立刻降到可以接受的水平。
5.2 状态编码压缩到极限
距离表本身还能再优化。因为最大距离只有11，小于16，所以理论上可以用4个bit存一个状态的距离，两个状态挤在一个字节里。这样3,674,160个状态的距离表可以从3.7MB压缩到1.9MB左右。
但4bit方案的代价是访问距离时需要多做一次位运算和可能跨越两个字节的分裂处理，代码复杂度上去了。我做了一版跑通之后，发现3.7MB的byte数组已经足够友好，最终没有采用4bit压缩——因为瓶颈不在内存而在GC，只要对象飞得少，几MB的差异无伤大雅。这个取舍分享出来，是希望大家明白：优化要以实际瓶颈为准，不要为了炫技引入复杂度。
5.3 打乱状态必须是合法可达状态
还有一件容易被忽视的事：测试用的打乱状态必须是从已还原状态通过合法转动生成的，绝不能随机给自己的数组赋值。
我最初为了快速测试，随手把pos数组乱填了一通，结果搜索直接搜不到解，一度以为BFS写错了。后来意识到，我构造的“打乱状态”根本不在魔方状态空间里——方向和不满足约束，等价于一个无法通过转动到达的幻影状态。
正确的打乱生成方式是：从已还原状态开始，随机执行若干个合法转动。我还特意在打乱生成时加了一个小逻辑：连续两次动作不允许出现同一面的正逆抵消（比如刚转了U，下一步不允许转U'），这样能避免无效打乱。
public long generateRandomScramble(int length) { long state = encodeSolvedState(); Move lastMove = null; Random random = new Random(); Move[] moves = Move.values(); for (int i = 0; i < length; i++) { Move move = moves[random.nextInt(moves.length)]; if (lastMove != null && move.toPlain() == lastMove.toPlain()) { continue; } state = applyMove(state, move); lastMove = move; } return state; }这里toPlain()返回的是动作对应的基本面，比如U、U2、Ui都返回U。判断同一面连续操作，是为了不产生“又恢复了原样”的无意义打乱。
5.4 正确性验证：回放测试比肉眼可靠
拿到一条解法序列，怎么确认它真的能还原魔方？靠肉眼盯着小命令行看是不现实的，我用的办法是“回放验证”：
- 把解法序列逐个动作施加到打乱状态上；
- 每步检查状态long和当前状态是否一致；
- 全部执行完后，判断最终状态是否等于已还原状态。
我随机生成了两万组测试用例，全部走这个流程，最终零失败。另外还做了一件事：把所有3,674,160个状态的“从打乱到还原”都走了一遍，确认每个状态都能在距离表指引下回到原点，才算彻底放心。
这种基于“状态可达+回放验证”的双重校验，比单纯跑几个例子更有说服力。程序可以输出一条说是“解法”的序列，但只有当你把序列重新作用到魔方上并精确还原，它才是真的解法。
6. 从“能解”到“秒解”：扩展玩法与实现边界
核心功能完整后，这个程序已经可以当作一个极简求解器使用了。但它还有不少可以继续折腾的空间，我列几个我试过或计划过的方向。
6.1 预计算表的序列化与加载
全量BFS虽然只有三四十秒，但每次启动都等这几十秒还是有点烦。更舒服的做法是：把距离表序列化到本地文件，程序启动时直接加载，实现真正意义上的“秒开秒解”。
具体实现完全没有技术含量：byte数组直接写文件，加载时一次性读入即可。3.7MB的文件对于现代磁盘几乎没有存在感。这样程序就从一个“每次要先热身”的搜索工具，变成了一个“随时待命”的查询工具。
6.2 从命令行到图形界面
我还想更进一步：给程序加上一个基于Swing的图形化交互界面。点击按钮转动魔方，实时显示当前状态，然后点“Solve”按钮瞬间弹出解法。这一步的主要工作量不在算法，而在把魔方展开图绘制出来，以及在点击和状态更新之间建立联动。
不过，做图形界面前要三思：核心算法和UI逻辑必须彻底解耦，否则后面每次优化算法都要连带改界面。我目前的做法是保留一个纯命令行版本，界面版本作为独立模块接口调用求解器，两边互不干扰。
6.3 从二阶走向三阶：这套思路的边界在哪
有人肯定会问：这套全量BFS方案能不能直接推广到三阶？答案是几乎不可能。
三阶魔方的状态数大约是4.3×10^19，即便使用最先进的两阶段算法和专门的硬件，也不可能全量建表。全量BFS的思路在三阶这个规模面前完全不成立。
但二阶程序里学到的建模思路、搜索策略、状态压缩经验，迁移到三阶时依然有价值——只是要把“全量预计算”换成“启发式搜索”或者“两阶段预计算+在线搜索”。这也是为什么我强烈推荐先用二阶练手：它让你用极低的成本把搜索算法和状态表示玩明白，之后再面对更大的状态空间，至少知道从哪里下刀。
6.4 关于“最优”两个字要说清楚
程序导出的解法是不是“全世界最短”？严格说，在我使用的9动作动作集内是最短的，标准六面动作集下的全局最优则可能更短，但差别通常非常小（最多一两步）。如果你追求严格的六面最优，需要把动作集扩展成完整18种，并重新处理整体旋转对齐问题，那套方案的复杂度会明显上一个台阶。
我最终保留了9动作集，是因为“极快求解”和“短解”已经满足绝大多数使用场景。对一个二阶魔方求解器来说，步数从11变成12根本不重要，重要的是你的解法是否合法、能否稳定复现、程序响应是否够快。这三条，9动作集全做到了。
我自己在没动手前，一直以为这套程序最难的是“搜索算法本身”，真正写完之后才发现，最折磨人的是状态表示的细节：朝向怎么算、锚点怎么固定、打乱怎么生成、距离表怎么存储。这些问题每一个都很小，但每一个出错都会让结果莫名其妙地不对。如果你也想写一个魔方还原程序，我的建议是不要急着套一个高深的算法，先把状态模型写到“能用单元测试覆盖”的程度，再往上加搜索。模型稳了，算法只是水到渠成的事。
