ハノイの塔の解き方で覚えることは、2つの手順だけです。これを交互に繰り返すと、円盤が何枚あっても、いちばん少ない手数で塔を移せます。この記事では、左の棒の塔を右の棒へ移す場合で説明します(ルールはハノイの塔とは?を見てください)。円盤には、小さい順に1、2、3…と番号を付けて呼びます。
解き方は2つの手順の繰り返し
- 奇数回目の手(1手目・3手目・5手目…): いちばん小さい円盤(1)を、決まった向きに1本となりへ動かす。
- 偶数回目の手(2手目・4手目・6手目…): 1以外の円盤で、動かせる手を指す。動かせる手は、いつも1つしかありません。
たったこれだけです。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より小さい円盤はないため)。
- 残りの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は全体の半分の手で動きますが、いちばん大きい円盤は1回しか動きません。大きい円盤を何度も動かしていたら、遠回りをしています。
- はじめは3枚か4枚で: 2つの手順が体に入るまでは、少ない枚数で何回か繰り返すのがおすすめです。慣れたら5枚、7枚と増やしましょう。
段数ごとの手順
段数ごとの手順と途中の形の目印は、次の記事にまとめています。
遊んで試してみる
下の盤で、2つの手順を試してみてください。棒を押すと、いちばん上の円盤を持ち上げ、別の棒を押すとそこへ置きます。最初は4枚(偶数)なので、1手目は1を中央へ動かします。
