ハノイの塔とは？ルール・解き方・最小手数の公式から世界滅亡の伝説まで徹底解説

「ハノイの塔」というパズルをご存じでしょうか。3本の柱と、大きさのちがう何枚かの円盤だけを使う、見た目はとてもシンプルなゲームです。

ところがこのパズル、ルールは小学生でも30秒で覚えられるのに、その奥には再帰や指数関数といった数学の美しさがぎっしり詰まっています。さらに「すべて移し終えると世界が滅亡する」という、とんでもなくスケールの大きな伝説まで背負っているのです。

この記事では、ハノイの塔のルールと解き方のコツ、最小手数を表す公式の仕組み、そして考案者がしかけた遊び心あふれる伝説の真相まで、まるごと徹底解説します。読み終えるころには、誰かに話したくなる雑学がいくつも増えているはずです。

ハノイの塔とは？3本の柱と円盤で遊ぶ数学パズル

ハノイの塔（英語でTower of Hanoi）は、フランスの数学者エドゥアール・リュカが1883年に発表したパズルです。木製のおもちゃとして売り出され、いまでは世界中の知育玩具やプログラミングの教科書に登場する、パズルの大定番になっています。

用意するのは3本の柱と、中央に穴のあいた大きさのちがう円盤が数枚。最初はすべての円盤が1本の柱に、大きいものが下、小さいものが上になるように積み重ねられています。これをそっくりそのまま別の柱へ移動させれば完成です。

ハノイの塔の3つのルール

円盤の動かし方には、次の3つのルールがあります。覚えることはこれだけです。

• 円盤は1回に1枚だけ動かす（2枚まとめて持ち上げるのはNG）
• 小さい円盤の上に、大きい円盤を載せてはいけない
• 円盤は必ず3本の柱のどれかに置く（柱以外の場所に一時的に置くのも禁止）

特に大事なのが2つ目のルールです。「大きい円盤は小さい円盤の上に乗れない」という制約があるおかげで、ただ移すだけのはずが急に頭を使うパズルへと変わります。小さい円盤がいつも邪魔になり、どかしてはまた戻す、という手間が次々と生まれるのです。

ハノイの塔の別名（ブラフマーの塔・ルーカスタワー）

ハノイの塔には、いくつかの呼び名があります。後ほど紹介する伝説にちなんだ「ブラフマーの塔」や「バラモンの塔」、そして考案者リュカの名前をとった「ルーカスタワー（Lucas' Tower）」などです。

ちなみに「ハノイ」はベトナムの首都の名前ですが、このパズルは実際のハノイの街とは直接の関係がありません。考案者が東洋風の神秘的な雰囲気を出すために名づけた、いわば演出だったといわれています。この名前の謎についても、後半の伝説のところで明らかにしていきます。

ハノイの塔の解き方とコツ｜再帰で考えれば攻略できる

枚数が増えると複雑に見えるハノイの塔ですが、ある考え方を知っておくと、驚くほどスッキリ解けるようになります。それが「再帰（さいき）」という発想です。まずは少ない枚数から見ていきましょう。

まずは3枚で試してみよう（最短7手）

円盤を小・中・大の3枚として、左の柱Aから右の柱Cへ移してみます。補助に使うのが真ん中の柱Bです。最短の手順は、次の7手になります。

1. 小をAからCへ動かす
2. 中をAからBへ動かす
3. 小をCからBへ動かす
4. 大をAからCへ動かす
5. 小をBからAへ動かす
6. 中をBからCへ動かす
7. 小をAからCへ動かす

これで3枚すべてがCへ移りました。ポイントは、4手目で一番大きい円盤を動かす前に、上の2枚を補助の柱Bへきれいにまとめている点です。この「まず上をどかす」という流れこそが、実はあらゆる枚数で共通する解き方の核になります。

再帰的な考え方が攻略のカギ

円盤がn枚あるときの手順は、次の3つのステップに分解できます。

• 一番下の円盤をのぞいた「上のn-1枚」を、先に補助の柱へ移す
• 残った「一番下の1枚」を、ゴールの柱へ移す
• 補助の柱に避けておいた「n-1枚」を、ゴールの柱へ移す

注目してほしいのは、1番目と3番目に出てくる「n-1枚を移す」という作業です。これはサイズが1枚少ないだけの、まったく同じ形のハノイの塔そのものです。大きな問題が、ひとまわり小さい同じ問題に化けるわけです。

この「自分自身と同じ形の小さな問題が中に現れる」構造を、数学やプログラミングでは再帰と呼びます。3枚が解ければ4枚も解け、4枚が解ければ5枚も解ける。ハノイの塔は、再帰という考え方を体で理解できる最高の教材なのです。

奇数枚・偶数枚で最初の一手が変わる

実は最短で解くとき、手はほとんど機械的に決まっています。一番小さい円盤は、つねに一定の向きへぐるぐると回り続けるのです。そして小さい円盤を動かさない手番では、残り2本の柱のあいだで動かせる手が1通りに決まります。

最初の一手をどちらへ動かすかは、円盤の総数で変わります。下のように覚えておくと、迷わず最短手順に入れます。

最小手数を表す公式「2のn乗-1」の仕組み

ハノイの塔の美しさが一番きわだつのが、この最小手数の話です。円盤がn枚のとき、最短で移すのに必要な手数は、ぴったり2ⁿ-1手になります。ここではその仕組みを、むずかしい式をできるだけ使わずに解きほぐしていきます。

円盤の枚数と最小手数の一覧

まずは具体的な数字を見てみましょう。円盤が1枚増えるごとに、手数がほぼ2倍にふくらんでいくのが分かります。

10枚でもう1,023手。たった10枚なのに千手を超えるとは、指数関数のふくらみ方のすごさが伝わってきます。一番下の64枚については、のちほど伝説のところでたっぷり触れます。

漸化式から公式「2のn乗-1」を導く

なぜ2ⁿ-1になるのでしょうか。さきほどの再帰の3ステップを思い出してください。n枚を移すには「n-1枚を移す手数」が2回と、「一番下の1枚を移す1手」が必要でした。n枚の最小手数を a_n で表すと、次の関係が成り立ちます。

a_n ＝ 2 × a_n-1 ＋ 1

1枚なら1手なので、a₁ ＝ 1 です。ここから2枚は2×1＋1＝3手、3枚は2×3＋1＝7手、4枚は2×7＋1＝15手と、芋づる式に求まっていきます。この式を整理すると、きれいに a_n ＝ 2ⁿ-1 という公式になります。再帰の考え方が、そのまま公式の証明になっているのです。

メルセンヌ数・二進法との美しい関係

2ⁿ-1という形の数は、数学では「メルセンヌ数」と呼ばれます。3、7、15、31…と続くこの数列は、巨大な素数の研究などにも顔を出す重要な数たちです。ハノイの塔の手数が、実は名前のついた由緒ある数だったわけです。

さらに面白いのが、二進法とのつながりです。手順を1手目、2手目…と数えていくと、k手目に動かす円盤は「kを二進数で書いたときの、一番下の桁の位置」で決まります。1手目（二進数で1）は一番小さい円盤、2手目（10）は2番目、4手目（100）は3番目、という具合です。ハノイの塔は、ただ数を1つずつ数えているのと同じ動きをしているのです。

数字の中にこんな規則が隠れているパズルが好きな方は、以下の記事もあわせてどうぞ。

ハノイの塔の由来と「世界の終わり」の伝説

考案者リュカと偽名アナグラムの謎

ハノイの塔を考えたのは、フランスの数学者エドゥアール・リュカ（1842年～1891年）です。フィボナッチ数列の研究や、巨大な素数を判定する方法で知られる、本物の一流数学者でした。

面白いのは、1883年にこのパズルを売り出したときの名義です。リュカは自分の名前を伏せ、「N.クラウス・ド・シャム」という架空の人物の名で発表しました。シャムとは、いまのタイの古い呼び名です。ところがこの「N. Claus de Siam」をよく見ると、「Lucas d'Amiens（アミアンのリュカ）」の文字を並べかえたアナグラムになっているのです。

遊び心はこれだけではありません。説明書に出てくる架空の大学「Li-Sou-Stian」も、リュカが教えていたパリの名門「Saint-Louis（サン＝ルイ）高校」のアナグラムでした。一流の数学者がしかけた、知的な目くらましだったわけです。

ブラフマーの塔とベナレスの寺院の伝説

ハノイの塔の説明書には、パズルの由来として、こんな壮大な伝説が添えられていました。

インドの聖地ベナレス（現在のヴァラナシ）の寺院に、3本のダイヤモンドの針が立っている。天地創造のとき、神ブラフマーはそのうちの1本に、64枚の純金の円盤を大きい順に積み上げた。僧侶たちは昼夜を問わず、ハノイの塔とまったく同じルールで円盤を別の針へ移し替え続けている。そしてすべての円盤を移し終えたとき、塔は崩れ、世界は終わりを迎える。こんな物語です。

黄金の円盤、ダイヤモンドの針、そして世界の終焉。パズルのおまけにしては、あまりにドラマチックな設定ですね。

伝説の真相｜64枚ならおよそ5849億年かかる

結論から言うと、この伝説はリュカ自身が創作したフィクションです。インドやベトナムに古くから伝わる話ではありません。パズルを神秘的に見せるための、いわば名コピーだったのです。

では、もし伝説が本当だったら、世界はいつ終わるのでしょうか。64枚の最小手数は2⁶⁴-1、つまり18,446,744,073,709,551,615手です。日本語にすると、およそ1844京手という、けた違いの数字になります。

仮に僧侶が1秒に1枚という超人的なスピードで休まず動かし続けたとしても、すべて移し終えるのにかかる時間はおよそ5849億年です。宇宙が誕生してから今までが約138億年ですから、その40倍以上かかる計算になります。世界の終わりを心配する必要は、どうやら当分なさそうですね。

ハノイの塔は何の役に立つ？応用と4本版の難問

ただのおもちゃに見えるハノイの塔ですが、その考え方は意外なほど広い分野で活躍しています。最後に、パズルの枠を超えた応用と、いまも研究が続く奥深い世界をのぞいてみましょう。

再帰アルゴリズムの代表的な教材

プログラミングを学ぶと、ほぼ必ずと言っていいほどハノイの塔が登場します。「大きな問題を、同じ形の小さな問題に分けて解く」という再帰の考え方が、これ以上ないほどきれいに表れるからです。実際、ハノイの塔を解くプログラムはほんの数行で書けてしまい、再帰の威力を実感できる入門教材として定番になっています。

計画力を測る心理検査にも使われる

ハノイの塔は、心理学や医療の現場でも使われています。先を読んで手順を組み立てる力、つまり計画力や実行機能を調べる検査として、「ハノイの塔課題」が知られているのです。よく似た「ロンドンの塔」という検査もあり、いずれも脳の前頭葉のはたらきを評価するのに役立てられています。シンプルなパズルが、人間の思考力を測るものさしになっているわけです。

棒が4本以上なら？100年越しに解かれた難問

ここまでは柱が3本の話でした。では柱を4本に増やすと、最小手数はどうなるのでしょうか。柱が増えれば円盤の逃がし場所も増えるので、もっと少ない手数で解けるようになります。

ところが、この4本版の「本当の最小手数」を求める問題は、長いあいだ数学者を悩ませてきました。4本版は「リーブのパズル」とも呼ばれ、最適と思われる解き方（フレーム・スチュワートのアルゴリズム）は早くから知られていたものの、それが本当に最小だと証明できなかったのです。

19世紀から続いたこの難問は、なんと2014年になってようやく決着しました。数学者ティエリ・ブシュが、4本版でその解き方が確かに最適であることを証明したのです。おもちゃのようなパズルの裏に、100年以上かけて解かれた本物の数学があったとは、驚きですね。

腕試し！ハノイの塔クイズ5問

ここまでの内容のおさらいです。答えはすぐ下のボックスに入れてあります。何問わかるか挑戦してみてください。

第1問：円盤が3枚のとき、最短で何手あれば移せるでしょう？

第2問：円盤が1枚増えると、最小手数はおよそ何倍になるでしょう？

第3問：考案者リュカが使った偽名「N. Claus de Siam」は、何を並べかえたものでしょう？

第4問：伝説で、神ブラフマーが積み上げた純金の円盤は何枚でしょう？

第5問：柱が4本のハノイの塔で、最適な解き方が証明されたのは何年でしょう？

よくある質問（FAQ）

Q. ハノイの塔は何歳くらいから遊べますか？

円盤が3枚なら、ルール自体は幼児でも理解できます。枚数を増やすほど難しくなるので、3枚から始めて、慣れたら4枚、5枚と段階的に増やすのがおすすめです。家族で「最短手数」を競っても盛り上がります。

Q. 最短手数で解かないとダメなのですか？

いいえ、自由に動かして完成させるだけでも立派なクリアです。ただ、最短を目指すと「2のn乗-1」という数学の規則が体感でき、ぐっと面白くなります。慣れてきたら最短手数に挑戦してみてください。

Q. 市販のハノイの塔は、円盤が何枚のものが多いですか？

木製のおもちゃでは、5枚から10枚のものが主流です。7枚（最短127手）や8枚（最短255手）あたりが、難しすぎず手応えもあって人気があります。

Q. なぜプログラミングの勉強で必ず出てくるのですか？

「同じ形の小さな問題に分けて解く」という再帰の考え方を、最も分かりやすく示せる例だからです。短いコードで動き、再帰の仕組みを実感できるため、入門の定番教材になっています。

Q. スマホやパソコンでも遊べますか？

はい、無料のアプリやブラウザで動くハノイの塔がたくさんあります。実物がなくても気軽に試せるので、まずは3枚から挑戦してみてください。

まとめ：シンプルなのに奥が深い名作パズル

ハノイの塔は、「円盤を1枚ずつ動かす」「大きい円盤を小さい円盤の上に置かない」という、たった2つの制約だけでできた、究極にシンプルなパズルです。

それでいて、その中には再帰という考え方、2のn乗-1という美しい公式、二進法やメルセンヌ数とのつながりまで隠れています。シンプルなルールから深い数学が湧き出してくる、見事な作品です。

さらに、考案者リュカがしかけた偽名のアナグラムや、世界の終わりを告げる壮大な伝説など、知れば誰かに話したくなるエピソードもたっぷり詰まっています。遊んで楽しく、語って面白い名作パズルです。

木製のおもちゃでも、スマホアプリでもかまいません。ぜひ一度、自分の手で円盤を動かして、その奥深さを味わってみてください。

この記事は、以下の資料を参考にしています。