解汉诺塔,要记住的只有两条步骤。交替重复它们,不管有多少个圆盘,都能以最少步数移塔。这篇文章以把左侧柱子上的塔移到右侧柱子为例来说明(规则请看什么是汉诺塔?)。圆盘按从小到大的顺序编号,叫作 1、2、3……

解法是两条步骤的重复

  1. 奇数步(第 1 步、第 3 步、第 5 步……):把最小的圆盘(1),朝固定的方向移到相邻的一根柱子。
  2. 偶数步(第 2 步、第 4 步、第 6 步……):走 1 以外的圆盘中能动的那一步。能走的步,永远只有 1 个。

就只有这么简单。1 每隔一步动一次,在这期间 1 以外的圆盘各动一次。

小圆盘绕行方向的决定方法

1 的移动方向,由圆盘个数决定。把 3 根柱子想成连成一圈,到了尽头就绕到另一头。把左侧的塔移到右侧时,顺序如下。

圆盘个数1 的移动顺序
奇数个(3、5、7……)左→右→中间→左……
偶数个(4、6、8……)左→中间→右→左……

记法是“奇数个的话,第 1 步直接把 1 放到想移过去的柱子”。偶数个的话,第 1 步放到不是目标的那一根(中间)。方向定下来之后,到最后都不要改变。

想移到中间柱子时,把表里的“右”和“中间”互换着想。

用 3 个圆盘来验证

3 个圆盘(奇数),所以 1 按“左 → 右 → 中间 → 左”的顺序绕行。金色的圆盘就是这一步移动的圆盘。

  1. 321 开始
  2. 321 第 1 步 1移到右侧
  3. 321 第 2 步 2移到中间
  4. 321 第 3 步 1移到中间
  5. 213 第 4 步 3移到右侧
  6. 123 第 5 步 1移到左侧
  7. 132 第 6 步 2移到右侧
  8. 321 第 7 步 1移到右侧

可以看出,第 1 步、第 3 步、第 5 步、第 7 步只是在移动 1,而第 2 步、第 4 步、第 6 步都是“1 以外唯一能动的那一步”。

偶数步只有一种走法的原因

偶数步时,比较没有放 1 的那两根柱子最上面的圆盘。只能把小的移到大的上面(或空柱子)。

  • 1 上面,什么圆盘都不能放(因为没有比 1 更小的圆盘)。
  • 剩下的 2 根柱子里,不能把大圆盘放到小圆盘上。

所以,能走的步永远只有 1 个。会犹豫的只有奇数步时 1 的方向,而这一点只要最初定好,之后不用想,手就会一步步走下去。

“先移开上面的,再搬大的”的思路

除了记住步骤,还有一种思路,是想想为什么这样就能解开。要把 n 个圆盘的塔从左侧移到右侧,只要分成:

  1. 把上面的 n−1 个圆盘,移到中间。
  2. 把最大的圆盘,搬到右侧。
  3. 把中间的 n−1 个圆盘,移到右侧。

这 3 个部分就行了。第 1 步和第 3 步是“移动少 1 个圆盘的塔”的问题,所以可以再用一次同样的思路。4 个圆盘就是“移开 3 个 → 搬 4 → 移回 3 个”,要移开 3 个,又是“移开 2 个 → 搬 3 → 移回 2 个”……这样可以分解成越来越小的问题。从这个思路,也能知道步数是 2ⁿ−1 次(最少步数公式)。

走到一半迷路时怎样重新理顺

就算忘了步骤,圆盘摆得乱七八糟,也不用担心。用下面的思路,从哪里都能重新理顺。

  1. 在还没有正确叠到右侧柱子上的圆盘里,找出最大的那个。这就是下一个要搬的圆盘。
  2. 要把这个圆盘搬到右侧,就得把比它小的圆盘全部集中到既不是它现在所在的柱子、也不是右侧柱子的、剩下的那 1 根上。
  3. 集中小圆盘,也是同样思路的重复。把集中的目的地当作“目标柱子”,从头再来。

窍门是从大圆盘开始,依次决定目的地。应用的“题目”模式(把乱放的圆盘摆成样本的形状的玩法),也可以用这个思路解开。

攻略窍门

  • 数步数:奇数步一定是动 1,所以只要知道是第几步,下一步该动哪个圆盘就不会犹豫。
  • 越大的圆盘越不动:1 在全部步数的一半里都在动,而最大的圆盘只动 1 次。如果大圆盘动了很多次,就是在绕远路。
  • 一开始用 3 个或 4 个圆盘:在两条步骤还没有记在身体里之前,建议用少一点的圆盘多重复几次。熟练之后,再增加到 5 个、7 个。

各层的步骤

各层的步骤和途中各阶段的标记形状,整理在下面这些文章里。

玩一玩来验证

请在下面的盘面里试试这两条步骤。点一下柱子,会拿起最上面的圆盘,再点另一根柱子,就会放到那里。一开始是 4 个圆盘(偶数),所以第 1 步要把 1 移到中间。

4321
0 步(最少 15 步)

把左边的塔整个移到右侧柱子。点击柱子即可拿起最上面的圆盘。