河內塔的解法,要記的只有兩個步驟。交替重複這兩個步驟,不論有幾個圓盤,都能用最少步數把塔移完。這篇文章以把左側柱子上的塔移到右側柱子為例來說明(規則請看什麼是河內塔?)。圓盤依由小到大稱為 1、2、3……號。

解法是兩個步驟的重複

  1. 奇數步(第 1 步、第 3 步、第 5 步……):把最小的圓盤(1),朝固定的方向移到相鄰的柱子。
  2. 偶數步(第 2 步、第 4 步、第 6 步……):走 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 更小的圓盤)。
  • 剩下的兩根柱子之間,不能把大圓盤放到小圓盤上。

所以,能移動的走法永遠只有一種。要煩惱的只有奇數步時 1 的方向,而這個只要一開始決定好,之後不用多想,步驟就能一路走下去。

「搬開上面的,再搬大的」的想法

除了背步驟之外,也有一種思考「為什麼這樣能解開」的方法。要把 n 個圓盤的塔從左邊移到右邊,只要分成下面三件事:

  1. 把上面的 n−1 個圓盤,搬開到中間。
  2. 把最大的圓盤,搬到右側。
  3. 把中間的 n−1 個圓盤,移到右側。

1 和 3 都是「移動少一個圓盤的塔」的問題,所以可以再用一次同樣的想法。4 個圓盤就是「搬開 3 個 → 搬 4 → 把 3 個放回去」,要搬開 3 個又是「搬開 2 個 → 搬 3 → 把 2 個放回去」……就這樣一直分成更小的問題。從這個想法,也能知道步數是 2ⁿ−1 步(最少步數公式)。

做到一半迷路時的重新整理方法

就算忘了步驟,讓圓盤散成亂七八糟的配置也沒關係。用下面的想法,不論從哪裡都能重新整理。

  1. 在還沒正確疊到右側柱子的圓盤中,找出最大的那一個。這就是接下來要搬的圓盤。
  2. 要把它搬到右側,必須先把比它小的圓盤全部集中到既不是它現在所在的柱子、也不是右側柱子的剩下那一根。
  3. 集中小圓盤,也是同樣想法的重複。把要集中的地方當成「目標柱子」,從頭再來一遍。

訣竅是從大的圓盤開始,依序決定它們的去處。App 的「題目」模式(把散亂的圓盤擺成樣本的形狀)也可以用這個想法來解。

破關的小訣竅

  • 數步數:奇數步一定是移動 1,所以只要知道現在是第幾步,就不會搞不清楚下一個該動哪個圓盤。
  • 越大的圓盤動得越少:1 在全部步數的一半都會動,但最大的圓盤只會動 1 次。如果你一直在移動大圓盤,就是在繞遠路。
  • 一開始先用 3 個或 4 個:在兩個步驟還沒記進身體之前,建議用比較少的圓盤個數重複練習幾次。熟練之後再增加到 5 個、7 個。

各層數的走法

各層數的走法和途中的形狀記號,整理在下面的文章裡。

玩玩看試試

請在下面的盤面試試這兩個步驟。點一下柱子,會拿起最上面的圓盤,再點另一根柱子就會放上去。一開始是 4 個圓盤(偶數),所以第 1 步要把 1 移到中間。

4321
0 步(最少 15 步)

把左邊的塔整個移到右側柱子。點一下柱子就能拿起最上面的圓盤。