ハノイの塔の解き方で覚えることは、2つの手順だけです。これを交互に繰り返すと、円盤が何枚あっても、いちばん少ない手数で塔を移せます。この記事では、左の棒の塔を右の棒へ移す場合で説明します(ルールはハノイの塔とは?を見てください)。円盤には、小さい順に1、2、3…と番号を付けて呼びます。

解き方は2つの手順の繰り返し

  1. 奇数回目の手(1手目・3手目・5手目…): いちばん小さい円盤(1)を、決まった向きに1本となりへ動かす。
  2. 偶数回目の手(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. 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より小さい円盤はないため)。
  • 残りの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は全体の半分の手で動きますが、いちばん大きい円盤は1回しか動きません。大きい円盤を何度も動かしていたら、遠回りをしています。
  • はじめは3枚か4枚で: 2つの手順が体に入るまでは、少ない枚数で何回か繰り返すのがおすすめです。慣れたら5枚、7枚と増やしましょう。

段数ごとの手順

段数ごとの手順と途中の形の目印は、次の記事にまとめています。

遊んで試してみる

下の盤で、2つの手順を試してみてください。棒を押すと、いちばん上の円盤を持ち上げ、別の棒を押すとそこへ置きます。最初は4枚(偶数)なので、1手目は1を中央へ動かします。

4321
0手(最少 15手)

左の塔を、右の棒へそっくり移そう。棒を押すと円盤を持ち上げます