汉诺塔最少要多少步？

n 层汉诺塔最少要 2ⁿ − 1 步：3 层 7 步、4 层 15 步、5 层 31 步、6 层 63 步、7 层 127 步、8 层 255 步。不可能更少：最大的盘至少要动一次，而它动之前，上面所有小盘必须先叠到第三根柱子上——这正好是少一层的汉诺塔，前后要做两遍。

3 层汉诺塔怎么走？

7 步：小盘到 C，中盘到 B，小盘到 B，大盘到 C，小盘到 A，中盘到 C，小盘到 C。简单说就是：先把两个小盘挪到中间柱，再把大盘搬过去，最后把两个小盘重新叠到大盘上。

有。单数步总是移动最小的盘，而且一直朝同一个方向转圈（层数为奇数时 A→C→B→A，层数为偶数时 A→B→C→A）；双数步做唯一一个不动最小盘的合法移动。本站测试验证了 1～10 层用这条规律都恰好走出 2ⁿ − 1 步的最短解。

能。任何摆法都还有解。点“提示”，游戏会从当前局面走最好的一步；棋盘下方会显示最少还要几步。无论盘子怎么摆，离目标都不会超过 2ⁿ − 1 步。

1883 年这个玩具上市时附带了一个故事：僧侣们不停地搬动 64 片金盘，搬完之时就是世界末日。按最少 18,446,744,073,709,551,615 步、每秒一步计算，大约要 5,845 亿年。

能。三根柱子都是很宽的点按区域，也可以用手指拖动盘子。每种层数当前这一局、用时和最佳成绩都保存在本机浏览器里，不用注册。

选层数：3 层只要 7 步，适合热身；每多一层，步数差不多翻一倍，8 层要 255 步。每种层数各自保存进度和最佳成绩。
拿起最上面的盘子：点一根柱子，最上面的盘子会抬起来；也可以按住这个盘子直接拖。
放到另一根柱子上：再点想放的柱子，或者把拖着的盘子在那根柱子上方松开。盘子只能放在空柱子上，或者放在比它大的盘子上。
把整座塔搬到 C 柱：所有盘子都按从大到小叠在最右边的 C 柱上就赢了。上方会同时显示你的步数和最少步数 2ⁿ − 1。
卡住了就撤销、提示或演示：撤销退回一步；提示会从当前局面替你走最好的一步；演示会把剩下的最短走法自动走完，方便看清规律。用过提示或演示的那一局不计入最佳记录。

下面是 3 层的最短走法，每一步一张图。留意两点：最小的盘每隔一步动一次；最大的盘只动一次，而且正好在正中间那一步。

开始

第 1 步：1 号盘 A→C

第 2 步：2 号盘 A→B

第 3 步：1 号盘 C→B

第 4 步：3 号盘 A→C

第 5 步：1 号盘 B→A

第 6 步：2 号盘 B→C

第 7 步：1 号盘 A→C

4 层也是同样的思路：先用 7 步把上面三层搬到中间的 B 柱，再把 4 号盘搬到 C 柱，最后再用 7 步把三层搬回来，一共 15 步。层数越多，就是把这个过程一层套一层地重复。

公式来自递归思路：搬 n 层 = 先搬走上面 n − 1 层 + 搬最大的一个 + 再把 n − 1 层搬回来，所以步数(n) = 2 × 步数(n − 1) + 1，算出来就是 2ⁿ − 1。

从最大的盘想起（递归法）。先问：还没到位的最大那个盘要去哪根柱子？它上面的盘子就必须先全部叠到剩下那根柱子上。再对这摞小一点的塔问同样的问题。这个方法从任何局面都能用，本站的“提示”按钮就是这样算的。
盯住最小的盘（口诀法）。单数步移动最小的盘，始终朝同一个方向转圈；双数步做唯一另一种合法移动。奇数层时小盘按 A→C→B→A 走，偶数层时按 A→B→C→A 走。
单号不压单号，双号不压双号。在最短走法里，单数号的盘从不直接放在单数号的盘上（双数同理）。如果你正要这么放，多半是在绕远路。
走到一半检查一下。完美解法走到第 2ⁿ⁻¹ − 1 步时，除了最大的盘，其余盘子应该全部叠在中间的 B 柱上。

汉诺塔由法国数学家卢卡斯（Édouard Lucas）在 1883 年推出，是计算机课讲“递归”最常用的例子，也常用来讲 2 的乘方、训练提前规划。给孩子玩可以从 3 层开始，7 步熟练以后加一层，再一起想想步数为什么差不多翻倍。

喜欢这种要提前想好几步的游戏，还可以试试孔明棋线上玩（跳到只剩一枚）、三国华容道（附横刀立马 81 步解法）和数字华容道。英文版页面与本页共用同一份存档。