河內塔的解法,要記的只有兩個步驟。交替重複這兩個步驟,不論有幾個圓盤,都能用最少步數把塔移完。這篇文章以把左側柱子上的塔移到右側柱子為例來說明(規則請看什麼是河內塔?)。圓盤依由小到大稱為 1、2、3……號。
解法是兩個步驟的重複
- 奇數步(第 1 步、第 3 步、第 5 步……):把最小的圓盤(1),朝固定的方向移到相鄰的柱子。
- 偶數步(第 2 步、第 4 步、第 6 步……):走 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 更小的圓盤)。
- 剩下的兩根柱子之間,不能把大圓盤放到小圓盤上。
所以,能移動的走法永遠只有一種。要煩惱的只有奇數步時 1 的方向,而這個只要一開始決定好,之後不用多想,步驟就能一路走下去。
「搬開上面的,再搬大的」的想法
除了背步驟之外,也有一種思考「為什麼這樣能解開」的方法。要把 n 個圓盤的塔從左邊移到右邊,只要分成下面三件事:
- 把上面的 n−1 個圓盤,搬開到中間。
- 把最大的圓盤,搬到右側。
- 把中間的 n−1 個圓盤,移到右側。
1 和 3 都是「移動少一個圓盤的塔」的問題,所以可以再用一次同樣的想法。4 個圓盤就是「搬開 3 個 → 搬 4 → 把 3 個放回去」,要搬開 3 個又是「搬開 2 個 → 搬 3 → 把 2 個放回去」……就這樣一直分成更小的問題。從這個想法,也能知道步數是 2ⁿ−1 步(最少步數公式)。
做到一半迷路時的重新整理方法
就算忘了步驟,讓圓盤散成亂七八糟的配置也沒關係。用下面的想法,不論從哪裡都能重新整理。
- 在還沒正確疊到右側柱子的圓盤中,找出最大的那一個。這就是接下來要搬的圓盤。
- 要把它搬到右側,必須先把比它小的圓盤全部集中到既不是它現在所在的柱子、也不是右側柱子的剩下那一根。
- 集中小圓盤,也是同樣想法的重複。把要集中的地方當成「目標柱子」,從頭再來一遍。
訣竅是從大的圓盤開始,依序決定它們的去處。App 的「題目」模式(把散亂的圓盤擺成樣本的形狀)也可以用這個想法來解。
破關的小訣竅
- 數步數:奇數步一定是移動 1,所以只要知道現在是第幾步,就不會搞不清楚下一個該動哪個圓盤。
- 越大的圓盤動得越少:1 在全部步數的一半都會動,但最大的圓盤只會動 1 次。如果你一直在移動大圓盤,就是在繞遠路。
- 一開始先用 3 個或 4 個:在兩個步驟還沒記進身體之前,建議用比較少的圓盤個數重複練習幾次。熟練之後再增加到 5 個、7 個。
各層數的走法
各層數的走法和途中的形狀記號,整理在下面的文章裡。
玩玩看試試
請在下面的盤面試試這兩個步驟。點一下柱子,會拿起最上面的圓盤,再點另一根柱子就會放上去。一開始是 4 個圓盤(偶數),所以第 1 步要把 1 移到中間。
