三根柱子和一摞锥形圆盘
棋盘上有三根柱子。圆盘大小各不相同，可以套到柱子上。开始时，整套圆盘都在一根柱子上，按大小排列，最大的在底部，最小的在顶部，因此这摞圆盘是一个锥形。 目标是把整座塔移到另一根柱子上。
三条规则
1. 每次只移动一个圆盘。 2. 一步就是取下一摞最上面的圆盘，放到另一摞上，或放到空柱上。 3. 大圆盘绝不能放在小圆盘上。 这三条规则就是整个游戏。在这些规则下，每个合法局面都是把圆盘分配到各柱上、同时每根柱子保持有序的一种方式。
最短解是 2ⁿ − 1
解出 n 个圆盘的塔所需的最少步数是 2ⁿ − 1。 一个圆盘需要 1 步。两个需要 3 步。三个需要 7 步，四个 15 步，五个 31 步。每增加一个圆盘，就把前一个解加倍，再加上搬动最大圆盘的那一步：如果 n − 1 个圆盘需要 T 步，那么 n 个圆盘需要 2T + 1 步。这个递推式正好等于 2ⁿ − 1。 PictorX 应用中最高的塔有八个圆盘，需要 255 步。不存在更短的合法路径。
递归如何运作
要把 n 个圆盘从起始柱移到目标柱，并把剩下的柱子当作辅助柱： 1. 把上面的 n − 1 个圆盘从起始柱移到辅助柱。 2. 把最大的圆盘从起始柱直接移到目标柱。 3. 把 n − 1 个圆盘从辅助柱移到目标柱，放在最大圆盘上面。 第 2 步是合法的，因为最大的圆盘可以放在任何柱子上。第 1 步和第 3 步是同一个谜题，只是少一个圆盘。递归调用到只剩一个圆盘时结束，它只移动一次。把递归展开，就得到 2ⁿ − 1 步，而且没有任何一步会把大圆盘放到小圆盘上。
64 个金盘的传说
法国数学家爱德华·卢卡斯于 1883 年提出了这个谜题。他随之讲了一个传说：在印度迦尸毗湿瓦纳特的一座神庙里，僧侣们按照同样的规则搬动一摞 64 个金盘。传说当最后一步完成时，世界就会毁灭。 六十四个圆盘需要 2⁶⁴ − 1 步：18,446,744,073,709,551,615。即使每秒走一步且从不出错、昼夜不停，也大约需要 5850 亿年。僧侣们是完成不了的。
在 PictorX 中玩
打开汉诺塔，起始柱上已经有一座四个圆盘的塔。最少需要十五步。把最上面的圆盘拖到另一根柱子上，或先点一根柱子再点目标柱子。按键 1、2、3 也有同样的作用。大圆盘放到小圆盘上会被拒绝。 “圆盘”可以从 1 调到 8，因此你可以用公式核对 1、3、7、15、31、63、127 和 255。“步”播放最短解中的一步。“求解”播放剩下的步骤。“观看 3 个圆盘”动态展示递归策略。“撤销”和“重做”可以在你的走法中前后移动。保存 PNG，或在 PictorX 编辑器中打开棋盘。
常见问题
汉诺塔的规则是什么？
每次移动一个圆盘。取下某根柱子最上面的圆盘，放到另一根柱子上。绝不能把大圆盘放在小圆盘上。整座塔从一根柱子出发，必须最终落在另一根柱子上。
最短解需要多少步？
2ⁿ − 1。一个圆盘 1 步，两个 3 步，三个 7 步，四个 15 步，五个 31 步。每多一个圆盘，就把前一个解加倍再加一步。
汉诺塔是谁发明的？
法国数学家爱德华·卢卡斯于 1883 年提出了它。迦尸毗湿瓦纳特的僧侣与 64 个金盘的故事，是他为这个谜题附上的传说。
64 个圆盘需要多久？
2⁶⁴ − 1 步，也就是 18,446,744,073,709,551,615 步。按每秒一步计算，大约需要 5850 亿年。
相关工具
汉诺塔
在浏览器中把一座圆盘塔移过三根柱子。每次一个圆盘，大盘绝不能压在小盘上。最短解是 2ⁿ − 1 步。
布丰投针
在浏览器中把针投到画有平行线的地板上。数一数相交次数，看布丰 1777 年的实验如何估算 π。
布丰投针
布丰 1777 年的投针问题：为什么投到平行线上的针能估算 π，短针概率 2l/(πd) 如何来自正弦曲线下的面积，以及这个实验为什么收敛得很慢。
乘法圆
把圆上的每个数连到它的倍数。在纸上、用粉笔或在木板上画出乘法表、心形线或绕线图形。
Collatz 猜想
在浏览器中探索 Collatz 3n+1 问题。追踪冰雹序列,生长几何 Collatz 树,并缩放连续的 Collatz 分形。
兰顿蚂蚁
在浏览器中运行兰顿蚂蚁。观察对称、混沌和 104 步的高速公路，再试试多色规则、多只蚂蚁、六边形网格和 Turmite。
准备好尝试了吗？
在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。
玩汉诺塔