解汉诺塔,要记住的只有两条步骤。交替重复它们,不管有多少个圆盘,都能以最少步数移塔。这篇文章以把左侧柱子上的塔移到右侧柱子为例来说明(规则请看什么是汉诺塔?)。圆盘按从小到大的顺序编号,叫作 1、2、3……
解法是两条步骤的重复
- 奇数步(第 1 步、第 3 步、第 5 步……):把最小的圆盘(1),朝固定的方向移到相邻的一根柱子。
- 偶数步(第 2 步、第 4 步、第 6 步……):走 1 以外的圆盘中能动的那一步。能走的步,永远只有 1 个。
就只有这么简单。1 每隔一步动一次,在这期间 1 以外的圆盘各动一次。
小圆盘绕行方向的决定方法
1 的移动方向,由圆盘个数决定。把 3 根柱子想成连成一圈,到了尽头就绕到另一头。把左侧的塔移到右侧时,顺序如下。
| 圆盘个数 | 1 的移动顺序 |
|---|---|
| 奇数个(3、5、7……) | 左→右→中间→左…… |
| 偶数个(4、6、8……) | 左→中间→右→左…… |
记法是“奇数个的话,第 1 步直接把 1 放到想移过去的柱子”。偶数个的话,第 1 步放到不是目标的那一根(中间)。方向定下来之后,到最后都不要改变。
想移到中间柱子时,把表里的“右”和“中间”互换着想。
用 3 个圆盘来验证
3 个圆盘(奇数),所以 1 按“左 → 右 → 中间 → 左”的顺序绕行。金色的圆盘就是这一步移动的圆盘。
- 开始
- 第 1 步 1移到右侧
- 第 2 步 2移到中间
- 第 3 步 1移到中间
- 第 4 步 3移到右侧
- 第 5 步 1移到左侧
- 第 6 步 2移到右侧
- 第 7 步 1移到右侧
可以看出,第 1 步、第 3 步、第 5 步、第 7 步只是在移动 1,而第 2 步、第 4 步、第 6 步都是“1 以外唯一能动的那一步”。
偶数步只有一种走法的原因
偶数步时,比较没有放 1 的那两根柱子最上面的圆盘。只能把小的移到大的上面(或空柱子)。
- 1 上面,什么圆盘都不能放(因为没有比 1 更小的圆盘)。
- 剩下的 2 根柱子里,不能把大圆盘放到小圆盘上。
所以,能走的步永远只有 1 个。会犹豫的只有奇数步时 1 的方向,而这一点只要最初定好,之后不用想,手就会一步步走下去。
“先移开上面的,再搬大的”的思路
除了记住步骤,还有一种思路,是想想为什么这样就能解开。要把 n 个圆盘的塔从左侧移到右侧,只要分成:
- 把上面的 n−1 个圆盘,移到中间。
- 把最大的圆盘,搬到右侧。
- 把中间的 n−1 个圆盘,移到右侧。
这 3 个部分就行了。第 1 步和第 3 步是“移动少 1 个圆盘的塔”的问题,所以可以再用一次同样的思路。4 个圆盘就是“移开 3 个 → 搬 4 → 移回 3 个”,要移开 3 个,又是“移开 2 个 → 搬 3 → 移回 2 个”……这样可以分解成越来越小的问题。从这个思路,也能知道步数是 2ⁿ−1 次(最少步数公式)。
走到一半迷路时怎样重新理顺
就算忘了步骤,圆盘摆得乱七八糟,也不用担心。用下面的思路,从哪里都能重新理顺。
- 在还没有正确叠到右侧柱子上的圆盘里,找出最大的那个。这就是下一个要搬的圆盘。
- 要把这个圆盘搬到右侧,就得把比它小的圆盘全部集中到既不是它现在所在的柱子、也不是右侧柱子的、剩下的那 1 根上。
- 集中小圆盘,也是同样思路的重复。把集中的目的地当作“目标柱子”,从头再来。
窍门是从大圆盘开始,依次决定目的地。应用的“题目”模式(把乱放的圆盘摆成样本的形状的玩法),也可以用这个思路解开。
攻略窍门
- 数步数:奇数步一定是动 1,所以只要知道是第几步,下一步该动哪个圆盘就不会犹豫。
- 越大的圆盘越不动:1 在全部步数的一半里都在动,而最大的圆盘只动 1 次。如果大圆盘动了很多次,就是在绕远路。
- 一开始用 3 个或 4 个圆盘:在两条步骤还没有记在身体里之前,建议用少一点的圆盘多重复几次。熟练之后,再增加到 5 个、7 个。
各层的步骤
各层的步骤和途中各阶段的标记形状,整理在下面这些文章里。
玩一玩来验证
请在下面的盘面里试试这两条步骤。点一下柱子,会拿起最上面的圆盘,再点另一根柱子,就会放到那里。一开始是 4 个圆盘(偶数),所以第 1 步要把 1 移到中间。
