ハノイの塔のルールと解き方｜最短手数と必ず解ける手順

ハノイの塔はどんなパズル？

ハノイの塔は、大きさの違う円盤を決まりを守りながら1枚ずつ動かすパズルです。左の棒に積んだ円盤を全部右の棒へ移したら完成です。

決まりはたった3つですが、円盤が増えるほど手数が増えていきます。最短の手数で解くには、先を読む力が必要です。

ハノイの塔で使う道具

ハノイの塔で使う道具は以下の通りです。

• 3本の棒（台に立てたもの）
• 大きさの違う円盤（3〜8枚くらい）

はじめは、全部の円盤を大きい順に左の棒へ積んでおきます。

円盤は真ん中に穴があいていて、棒に通して積み重ねます。この記事では、3本の棒を「左の棒」「真ん中の棒」「右の棒」と呼びます。

ハノイの塔のルール

ハノイの塔のルールを紹介します。

ハノイの塔のゴール

全部の円盤を同じ順番のまま右の棒へ移したら完成。

完成までの手数（円盤を動かした回数）が少ないほど上手です。それより少なくできない手数を「最短手数」と言います。

①1回に動かせるのは1枚だけ

円盤は1回に1枚ずつ動かします。

2枚以上をまとめて動かすことはできません。

②動かせるのは一番上の円盤だけ

動かせるのは、それぞれの棒の一番上にある円盤だけです。

下の円盤を先に抜き出すことはできません。

③小さい円盤の上に大きい円盤は置けない

円盤を置けるのは、空いている棒か、自分より大きい円盤の上だけです。

例えば、下の画像の左のように、大きい円盤の上に小さい円盤は置けます。右のように、小さい円盤の上に大きい円盤は置けません。

この3つの決まりを守れば、どの棒へ動かしてもOKです。真ん中の棒は、途中の置き場所として自由に使えます。

ハノイの塔の解き方

ハノイの塔は、決まった手順で動かせば、何枚でも必ず最短で解けます。少ない枚数から順に紹介します。

①3枚は7手で解ける

円盤が3枚の時、最短手数は7手です。

下の表の順に動かします。（小・中・大は円盤の大きさ）

3手目で、小と中が真ん中の棒にまとまります。その後、大を右の棒へ動かせるようになります。

②4枚は「3枚を2回」で解ける

4枚の時は、上の3枚を真ん中へ移し、一番大きい円盤を右へ動かし、3枚を右へ移します。

3枚を移すのは7手なので、4枚は7＋1＋7＝15手になります。上の3枚を1つのかたまりと考えると、分かりやすいです。

③5枚以上も同じ考え方で解ける

何枚でも「上の塔を真ん中へ → 一番大きい円盤を右へ → 塔を右へ」のくり返しで解けます。

例えば、5枚なら15＋1＋15＝31手です。このように、1枚増えるごとに「前の手数の2倍＋1」手になります。

④1手目は枚数で決まる

枚数が奇数なら右の棒へ、偶数なら真ん中の棒へ、一番小さい円盤を動かします。

例えば、3枚・5枚・7枚なら右の棒へ、4枚・6枚・8枚なら真ん中の棒へ置きます。逆に置くと、どこかで遠回りになります。

⑤小さい円盤は同じ向きに回す

最短の手順では、1手おきに、一番小さい円盤を同じ向きに動かします。

奇数枚なら「左 → 右 → 真ん中 → 左…」、偶数枚なら「左 → 真ん中 → 右 → 左…」の順に回ります。

小さい円盤を動かさない手は、置ける動かし方が1つしかありません。小さい円盤を回す手と、その1つの手を交互にくり返せば、何枚でも最短で解けます。

ハノイの塔の最短手数

ハノイの塔の最短手数は以下の通りです。

円盤がn枚の時、最短手数は「2のn乗−1」手です。

例えば、4枚なら2×2×2×2−1＝15手です。1枚増えるごとに、手数は約2倍になります。

円盤の数は「段」で数えることもあります。例えば、「5段」は円盤が5枚のことで、最短手数は31手（7段なら127手）です。

公式の求め方（漸化式）と、これより少なくできない理由は『ハノイの塔の最短手数の公式』の記事で解説しています。

ハノイの塔の伝説と由来

ハノイの塔は、フランスの数学者エドゥアール・リュカが、1883年に発表したパズルです。名前の「ハノイ」は、ベトナムの首都の名前です。

このパズルには、次のような言い伝えが添えられていました。

インドの寺院で、僧侶たちが64枚の金の円盤をこの決まりで動かし続けていて、全部を移し終えた時、世界が終わる。

この話は、パズルを広めるために作られたと考えられています。64枚の最短手数は約1845京手で、1秒に1手動かしても約5845億年かかります。

ハノイの塔の変わりルール

ハノイの塔でよく遊ばれる変わりルールを2つ紹介します。

4本の棒

4本の棒とは、置き場所の棒を1本増やすルールです。左端の棒の円盤を全部右端の棒へ移したら完成です。

棒が1本増えるだけで、最短手数はぐっと減ります。最短手数は以下の通りです。

4本の棒の最短手数は、3本の時のような短い式では表せません。この数が最短だと証明されたのは、2014年のことです。

隣の棒だけ

隣の棒だけとは、円盤を隣の棒へしか動かせないルールです。左の棒から右の棒へは、必ず真ん中の棒を通ります。

最短手数は「3のn乗−1」手で、3枚でも26手、4枚なら80手かかります。何度も同じ円盤を往復させるので、根気が必要です。

ハノイの塔を解くコツ

3本の棒のふつうのルールで、最短で解くコツを5つ紹介します。

1. 一番大きい円盤から考える

   一番大きい円盤を右へ動かせるのは、他の円盤が全部真ん中の棒にある時だけです。まずは「上の円盤を全部真ん中へ」を目指しましょう。

2. 1手目は枚数で決める

   枚数が奇数なら右の棒へ、偶数なら真ん中の棒へ、一番小さい円盤を置きます。1手目を間違えると、どこかで遠回りになります。

3. 奇数番目の手は小さい円盤

   最短で解く時は、1手目・3手目・5手目…と、1手おきに一番小さい円盤を動かします。迷ったら、今が何手目かを数えましょう。

4. 小さい円盤は同じ向きに回す

   一番小さい円盤は、いつも同じ向きに棒を回ります。向きを変えると、手数が増えてしまいます。

5. 少ない枚数から順に増やす

   3枚の7手を何度か解いてから、4枚・5枚と増やしましょう。3枚の動きは、大きな塔の中で何度もくり返されます。

当サイトのハノイの塔で選べる遊び方

当サイトのハノイの塔では、円盤を3〜10枚から選べます。「4本の棒」「隣の棒だけ」のルールでも遊べます。

次の1手を矢印で教える「ヒント」と、今の並びから完成まで自動で動かす「お手本」もあります。手順を覚えたい時に使いましょう。