汉诺塔是递归思想最经典的载体。三柱版本的最优解是 2^n – 1 步，任意学过递归的人倒背如流。但只要把柱子数从 3 改成 4，问题立刻变得完全不同：三柱的解有严格的递归结构，四柱的解至今没有被完全证明——1974 年 Frame 与 Stewart 提出的分治策略被认为是最优的，却依然是一个未解猜想。本文用 Java 完整实现 Frame-Stewart 算法，并把它做成一个可视化小游戏，读者可以直观看到四柱汉诺塔的步数比三柱少了多少。
一、问题建模：从三柱到四柱
三柱汉诺塔的经典递归可以概括为三个动作，设要把 n 个盘子从 A 借助 B 移到 C：
- 把上面 n-1 个盘子从 A 移到 B（借助 C）
- 把最底下的第 n 个盘子从 A 移到 C
- 把 n-1 个盘子从 B 移到 C（借助 A）
因此 T(n) = 2T(n-1) + 1，解得 T(n) = 2^n – 1。这个解法的关键在于”辅助柱”只有一根，我们无法把盘子”暂存”到别处，只能一次挪一整堆。
四柱场景下多了 D 这根空闲柱，思路自然变成：先把顶部 k 个盘子搬到 D（在 A、B、D 三根柱子之间做三柱搬运），再把剩余 n-k 个盘子搬到 C（此时 D 被占，只剩 A、B、C 三根柱子可用，即标准三柱问题），最后把 k 个盘子从 D 搬到 C（又变回三柱问题）。
于是得到递推式：
T(n, 4) = min over 1 <= k < n of [ T(k, 4) + 2^(n-k) – 1 + T(k, 4) ]
简化写作：
T(n, 4) = min over k [ 2 * T(k, 4) + 2^(n-k) – 1 ]
这个式子就是 Frame-Stewart 算法的核心。注意等号后出现的是 T(k, 4) 两次，说明顶部 k 个盘子的搬运仍然可以在四根柱子中进行，这就是”递归分割”的含义——它不是一次性把问题降为三柱，而是反复利用多出来的那根柱子。
二、Frame-Stewart 数值验证：为什么它不是 2*2^n
很多人直觉认为四柱汉诺塔大约是 2^n 的一半步数，但事实并非如此。Frame-Stewart 得到的渐进阶是 O(2^(sqrt(2n)))，是一个准多项式级别的量，远优于纯指数。
下面这个程序用 long 计算小规模 n 下的最优 k 分割点与步数，并和三柱解做对比：
import java.util.ArrayList;
import java.util.List;
/**
* Frame-Stewart 四柱汉诺塔：递推求解与最优分割点记录
*/
public class FrameStewart {
/** 记录每个 n 对应的最优分割点 k，便于打印决策过程 */
private final List<Integer> bestSplit = new ArrayList<>();
/**
* 计算 n 个盘子、pegs 根柱子下的 Frame-Stewart 步数
* 仅对 pegs == 4 使用本递推；pegs == 3 退化为 2^n - 1
*/
public long solve(int n, int pegs) {
bestSplit.clear();
return solveRec(n, pegs);
}
private long solveRec(int n, int pegs) {
if (n == 0) {
return 0;
}
if (pegs == 3) {
// 三柱问题有闭式解，直接返回，避免无谓递归
return (1L << n) - 1;
}
long best = Long.MAX_VALUE;
int bestK = 1;
// 枚举顶部 k 个盘子的切分位置
for (int k = 1; k < n; k++) {
// 两次 T(k) 表示顶部 k 个盘子两次在四柱环境中搬运
long cand = 2 * solveRec(k, pegs) + (1L << (n - k)) - 1;
if (cand < best) {
best = cand;
bestK = k;
}
}
bestSplit.add(bestK);
return best;
}
public static void main(String[] args) {
for (int n = 1; n <= 20; n++) {
long four = new FrameStewart().solve(n, 4);
long three = (1L << n) - 1;
System.out.printf("n=%2d 三柱=%7d 四柱=%7d 节省 %.1f%%%n",
n, three, four, 100.0 * (three - four) / three);
}
}
}
运行后会看到：n=10 时四柱只需 49 步，三柱需要 1023 步；n=20 时四柱约 289 步，三柱要 1048575 步。差距随 n 增长而急剧放大。
需要提醒一个性能细节：上面的递归是朴素写法，每层都重复计算 T(k)，复杂度会退化到接近 O(n^2) 次子调用（n 很小所以无感，但若 n 上千就应当先打表）。更稳妥的做法是自底向上预处理一个 dp 数组，把 T(0..n-1) 从小到大算完，再在 O(n) 时间内取最小值。
三、把最优步数变成可执行的移动序列
只知道步数是不够的，游戏需要真的把盘子搬动。Frame-Stewart 的移动序列构造与递推结构严格对应：
- 阶段一：把顶部 k 个盘子从源柱搬到辅助柱（四柱递归）
- 阶段二：把底下 n-k 个盘子从源柱搬到目标柱（三柱经典递归）
- 阶段三：把 k 个盘子从辅助柱搬到目标柱（四柱递归）
关键点在于”可用柱集合”要显式传递。阶段一可用 {src, aux, target, spare}，阶段二只能用 {src, target, spare}，阶段三可用 {aux, target, src, spare}。如果实现时误把某根柱子重复计入，就会生成非法移动。
import java.util.ArrayList;
import java.util.List;
/**
* 生成四柱汉诺塔的完整移动序列（Frame-Stewart 策略）
*/
public class HanoiMover {
/** 一次移动：from -> to */
public record Move(int from, int to) {
@Override
public String toString() {
return String.format("%c -> %c", 'A' + from, 'A' + to);
}
}
private final List<Move> moves = new ArrayList<>();
public List<Move> move(int n, int src, int dst, int[] others) {
if (n == 0) {
return moves;
}
if (others.length == 1) {
// 只有一根辅助柱：标准三柱递归
int aux = others[0];
move(n - 1, src, aux, new int[]{dst});
moves.add(new Move(src, dst));
move(n - 1, aux, dst, new int[]{src});
return moves;
}
// 四柱情形：others 长度为 2，取第一个作为临时堆放柱
int spare = others[0];
int rest = others[1];
int k = bestSplitFor(n);
// 阶段一：顶部 k 个盘子搬到 spare（四柱环境：其余为 src/dst/rest）
move(k, src, spare, new int[]{rest, dst});
// 阶段二：剩余 n-k 个盘子搬到 dst（三柱环境：只剩 rest 可作辅助）
moveSub(n - k, src, dst, rest);
// 阶段三：k 个盘子从 spare 搬到 dst
move(k, spare, dst, new int[]{rest, src});
return moves;
}
/** 阶段二：纯三柱搬运，独立实现以避免误用四柱递归 */
private void moveSub(int n, int src, int dst, int aux) {
if (n == 0) {
return;
}
moveSub(n - 1, src, aux, dst);
moves.add(new Move(src, dst));
moveSub(n - 1, aux, dst, src);
}
/** 与 FrameStewart 中 bestSplit 完全一致的分割点计算 */
private int bestSplitFor(int n) {
long best = Long.MAX_VALUE;
int bestK = 1;
long[] dp = new long[n + 1];
for (int i = 1; i <= n; i++) {
if (i == 1) {
dp[i] = 1;
continue;
}
long cur = Long.MAX_VALUE;
for (int k = 1; k < i; k++) {
long cand = 2 * dp[k] + (1L << (i - k)) - 1;
if (cand < cur) {
cur = cand;
}
}
dp[i] = cur;
}
for (int k = 1; k < n; k++) {
long cand = 2 * dp[k] + (1L << (n - k)) - 1;
if (cand < best) {
best = cand;
bestK = k;
}
}
return bestK;
}
public static void main(String[] args) {
HanoiMover m = new HanoiMover();
List<Move> list = m.move(5, 0, 2, new int[]{1, 3});
System.out.println("总步数 = " + list.size());
list.forEach(System.out::println);
}
}
这里用 record 承载移动指令，配合 int[] others 显式表达”当前可用的柱集合”，可以避免递归中柱子角色混乱这个最常见的 bug。
四、游戏化：用图形界面观察策略差异
把上面的引擎接到 Swing 画面上，就能得到一个可玩的汉诺塔小游戏：玩家手动拖拽，程序同时显示 Frame-Stewart 给出的最优步数与当前步数。玩家会明显感觉到四柱版本”能用更少的步数”，却不容易凭直觉找到那个最优的 k。
import javax.swing.*;
import java.awt.*;
import java.util.List;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* 四柱汉诺塔可视化：动画播放 Frame-Stewart 最优解
*/
public class HanoiPanel extends JPanel {
private static final int PEGS = 4;
private static final int N = 6;
private final Deque<Integer>[] pegs = new Deque[PEGS];
private int total;
public HanoiPanel() {
setPreferredSize(new Dimension(900, 480));
for (int i = 0; i < PEGS; i++) {
pegs[i] = new ArrayDeque<>();
}
// 盘子用尺寸表示，最大的在底部
for (int i = N; i >= 1; i--) {
pegs[0].push(i);
}
}
/** 执行一步移动，并校验合法性：只能移动柱顶盘子，且目标柱顶必须更大 */
public boolean applyMove(int from, int to) {
if (pegs[from].isEmpty()) {
return false;
}
int disk = pegs[from].peek();
if (!pegs[to].isEmpty() && pegs[to].peek() < disk) {
return false;
}
pegs[from].pop();
pegs[to].push(disk);
return true;
}
public void play(List<HanoiMover.Move> seq) {
total = seq.size();
new SwingWorker<Void, Integer>() {
@Override
protected Void doInBackground() throws Exception {
for (HanoiMover.Move mv : seq) {
applyMove(mv.from(), mv.to());
publish(1);
Thread.sleep(120);
}
return null;
}
@Override
protected void process(List<Integer> chunks) {
repaint();
}
}.execute();
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
int w = getWidth();
int panelW = w / PEGS;
g.setColor(Color.DARK_GRAY);
g.fillRect(0, 400, w, 12);
for (int p = 0; p < PEGS; p++) {
int cx = panelW * p + panelW / 2;
g.setColor(Color.GRAY);
g.fillRect(cx - 4, 60, 8, 340);
int level = 0;
for (int disk : pegs[p]) {
int dw = 30 + disk * 22;
g.setColor(new Color(60 + disk * 28 % 180, 120, 200 - disk * 20 % 160));
g.fillRect(cx - dw / 2, 392 - level * 26, dw, 22);
level++;
}
g.setColor(Color.BLACK);
g.drawString(String.valueOf((char) ('A' + p)), cx - 4, 40);
}
g.setColor(Color.BLUE);
g.drawString("最优步数(Frame-Stewart) = " + total, 20, 24);
}
public static void main(String[] args) {
JFrame f = new JFrame("四柱汉诺塔 — Frame-Stewart");
HanoiPanel p = new HanoiPanel();
f.add(p);
f.pack();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setVisible(true);
HanoiMover m = new HanoiMover();
p.play(m.move(N, 0, PEGS - 1, new int[]{1, 2}));
}
}
五、正确性验证：不只看步数，还要看合法性
手写汉诺塔最容易犯的错误是”步数对了但移动非法”。一个可靠的自检方式是模拟执行整条序列，用三组断言把关：起点柱非空、目标柱顶盘更大、最终状态全部落在目标柱。下面这段验证代码可以直接放进单元测试。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
public class HanoiVerifier {
public static void verify(List<HanoiMover.Move> seq, int n, int pegsCount, int dst) {
Deque<Integer>[] pegs = new Deque[pegsCount];
for (int i = 0; i < pegsCount; i++) {
pegs[i] = new ArrayDeque<>();
}
for (int i = n; i >= 1; i--) {
pegs[0].push(i);
}
for (int step = 0; step < seq.size(); step++) {
HanoiMover.Move mv = seq.get(step);
if (mv.from() < 0 || mv.from() >= pegsCount
|| mv.to() < 0 || mv.to() >= pegsCount) {
throw new IllegalStateException("第 " + step + " 步柱子下标越界: " + mv);
}
if (pegs[mv.from()].isEmpty()) {
throw new IllegalStateException("第 " + step + " 步源柱为空: " + mv);
}
int disk = pegs[mv.from()].peek();
if (!pegs[mv.to()].isEmpty() && pegs[mv.to()].peek() < disk) {
throw new IllegalStateException("第 " + step + " 步大盘压小盘: " + mv);
}
pegs[mv.from()].pop();
pegs[mv.to()].push(disk);
}
if (pegs[dst].size() != n) {
throw new IllegalStateException("终态未全部落在目标柱, 实际 " + pegs[dst].size());
}
System.out.println("校验通过：共 " + seq.size() + " 步，序列合法且完成搬运");
}
}
把 bestSplitFor 的错误版本（比如误用 10 * dp[k] 系数）喂给这个验证器，会在第一步就抛出”源柱为空”，这类错误用肉眼看步数很难发现，用验证器却一目了然。
六、复杂度与工程取舍
| 维度 | 三柱 | 四柱（Frame-Stewart） |
|---|---|---|
| 步数渐进 | 2^n – 1，纯指数 | O(2^(sqrt(2n)))，准多项式 |
| 递推依赖 | 单一子问题 | 两层子问题 + 枚举 k |
| 求最优 k | 无需枚举 | 每层 O(n) 枚举 |
| 移动序列构造 | 直接递归 | 三阶段拼接，需显式柱集合 |
工程上要注意三点。第一，步数计算与序列生成必须共享同一份分割点逻辑，否则会出现”显示的步数与实际播放步数不一致”的诡异现象——本文用 bestSplitFor 做统一入口就是为了规避这一点。第二，n 较大时先用动态规划打表求 T(0..n)，再构造序列，避免朴素递归的重复子问题。第三，如果只是展示用，n 取 4 到 6 已足够让观众感受到最优性，盘子再多动画时间会失控。
值得一提的是，”Frame-Stewart 是最优”目前仍是未证明的猜想。1990 年代以来的大量计算实验都支持它，但严格的数学下界尚未闭环。这意味着：如果你在游戏中给出的”最优步数”稍显神妙，它确实是当前人类已知最好的答案，而不是平凡的数学事实。
七、小结
四柱汉诺塔用一个极简的规则变化，把”背下来的递归模板”变成了真正的算法设计题。本文完成了三件事：把问题抽象为 T(n) = min_k [2T(k) + 2^(n-k) - 1] 的递推，用 Java 实现步数计算与移动序列构造，再用可视化与验证器保证结果既好看又合法。真正值得带走的经验是那套”显式传递可用柱集合 + 双份分割点逻辑 + 模拟执行断言”的工程习惯——它比记住任何一个公式都更耐用。
