ハノイの塔の遊び方は?
左の棒に積まれた円盤を、1枚ずつ動かして右の棒へ同じ順番のまま積み直せばクリアです。大きい円盤を小さい円盤の上に置くことはできません。
フランスの数学者エドゥアール・リュカが1883年に発表したパズルで、今でも数学やプログラミングの授業で「再帰」を学ぶときの定番の例になっています。
ルールは?
- 1枚ずつ: 動かせるのは、それぞれの棒のいちばん上の円盤だけです。
- 小さいものを大きいものの上に: 円盤は空の棒か、自分より大きい円盤の上にだけ置けます。小さい円盤の上には置けません。
- ゴール: 右の3番の棒に塔をまるごと積み直します。
- 星: 最短手数なら星3つ、その1.5倍までなら星2つ、それより多ければ星1つです。
最短手数は何手ですか?
円盤が n 枚のとき、最短手数は2n - 1手です。3枚なら7手、10枚なら1,023手です。
いちばん大きい円盤で考えてみましょう。それを右の棒に移す前に、上にのっている n - 1 枚の小さい円盤をまん中の棒にどけておく必要があります。そこで大きい円盤を1回動かし、n - 1 枚の小さい円盤をその上に戻します。つまり n 枚の手数はn - 1 枚の手数の2倍に1を足したものです。1枚なら1手、2枚なら3手、3枚なら7手、4枚なら15手となり、まとめると2n - 1になります。いちばん大きい円盤は小さい円盤がすべてどいたときにしか動かせないので、これより短い方法はありません。
| 円盤 | 最短手数 |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1,023 |
最短手数で解くには?
- 最初の一手は枚数で決める。 奇数枚なら、いちばん小さい円盤をまずゴールの棒へ。偶数枚なら、まん中の棒へ動かします。
- いちばん小さい円盤は1手おきに動かし、いつも同じ向きに回していきます。
- その間の手は、小さい円盤以外で動かせる手がひとつだけあります。それを動かしましょう。
- 迷ったら、いちばん大きい円盤を考える。 それを動かすには、上にあるものを全部ほかの1本に集めなければなりません。
自動で解くはどう動きますか?
今の円盤の並びから、最短の手数で残りを解いてくれます。速さは1倍から16倍まで変えられ、最初から解かせるとちょうど2n - 1手で終わります。
考え方は上と同じです。いちばん大きい円盤がまだゴールの棒になければ、小さい円盤をあいている棒にどけてから大きい円盤を動かし、小さい円盤をその上へ戻します。小さい円盤を動かすときも、ひと回り小さい大きさで同じ手順をくり返します。
64枚の塔を僧侶たちが移し終えたとき世界が終わる、という伝説があります。それには264 - 1手、およそ1800京手が必要で、1秒に1手でも約5850億年かかります。自動で解くを使ったゲームは記録に残りません。円盤の枚数ごとのベスト記録はこのブラウザに保存されます。