3本のポールと大きさの違う円盤だけの単純なパズルなのに、円盤が増えると手数は爆発的に増えていく——ハノイの塔は、コンピュータ科学とAIの世界で「問題解決の考え方」を学ぶ定番教材です。この記事では、ルールと最小手数の法則、AIの文脈での意味をやさしく解説します。
📖 ひと言でいうと
ハノイの塔とは、3本のポールの間で、大小の円盤をルールに従ってすべて移し替えるパズルです。ルールは「1回に動かせる円盤は1枚だけ」「小さな円盤の上に大きな円盤は乗せられない」の2つだけ。単純なルールから複雑な手順が生まれるため、探索やアルゴリズム（特に再帰）の練習問題として使われます。荷物の積み替えにたとえるなら、「上の荷物からしか動かせず、大きい箱を小さい箱の上に置けない」制約の中で、荷物の山をそっくり隣へ移す作業です。
🖼 1枚でわかるハノイの塔
📘 対策テキストの説明
円盤と3本のポールを用いたパズルの一種である。「1回に動かせる円盤の枚数は1枚のみ」「小さな円盤の上に大きな円盤を乗せることはできない」というルールに従って、全ての円を右端に移動させる。このパズルは、再帰的なアルゴリズムやプログラミングの教材としてよく用いられ、計算機科学や人工知能の分野でも重要な役割を果たしている。円盤の枚数がn枚である時、最小の手数は「（2^n）-1」回であることが知られており、この性質を利用して様々な問題解決アプローチや最適化手法を学ぶことができる。
押さえるべき点は3つです。①ルールは「1回1枚」「大が小の上に乗れない」の2つ。②最小手数は円盤n枚に対して(2^n)-1回という美しい法則がある。③このパズルは再帰的なアルゴリズムの教材として、コンピュータ科学・AI分野で広く使われてきた、という位置づけです。「2のn乗マイナス1」という式は、そのまま数値を問う形で出題できるため要注意です。
🔍 しっかり理解する
最小手数 (2^n)-1 の意味
円盤の枚数を増やしてみると、最小手数は次のように増えます。1枚なら1回、2枚なら3回、3枚なら7回、4枚なら15回、10枚なら1,023回。1枚増えるごとに手数は「約2倍+1」になり、指数関数的に増加します。
これはまさに、探索・推論の章の主役である組合せ爆発のミニチュアです。ルールも道具も極めて単純なのに、規模（n）が少し増えるだけで作業量が急増する——「単純な問題でも規模が大きくなると手に負えなくなる」ことを体感できるからこそ、ハノイの塔は教材として選ばれ続けています。
再帰的な解き方——大きな問題を小さな同じ問題に分ける
ハノイの塔の解法は「再帰」の考え方そのものです。n枚をAからCへ移す問題は、次の3ステップに分解できます。
①と③は「n-1枚のハノイの塔」という、元と同じ形の小さな問題です。小さな問題の答えを組み合わせれば大きな問題が解ける——この「自分自身を呼び出す」構造が再帰的アルゴリズムです。
手数の法則もこの分解から導けます。n枚の最小手数は「n-1枚の最小手数（①）＋1手（②）＋n-1枚の最小手数（③）」、つまり n枚の手数 = (n-1枚の手数)×2 + 1 です。1枚の手数1回から順に計算すると 1、3、7、15…となり、一般式 (2^n)-1 が確かめられます。公式を丸暗記するのではなく、「退避→最大を移動→戻す」という構造から式が出てくることを理解しておくと、試験でも安心です。
AIの文脈での位置づけ——トイ・プロブレム
ハノイの塔は、ルールと目標が明確に定義された、いわゆるトイ・プロブレム（おもちゃの問題）の代表例です。初期のAI研究は、探索によってこうしたパズルを解くことに成功し、大きな期待を集めました。一方で、トイ・プロブレムが解けても、条件があいまいで複雑な現実の問題はそのままでは解けないことが、後に第1次AIブームの限界として認識されていきます。ハノイの塔は「探索の力」と「その限界」の両方を象徴する存在なのです。
💡 具体例で考える
3枚の円盤（小・中・大）で最小手数7回を実際にたどってみましょう。左端Aから右端Cへ移すには、「小をCへ→中をBへ→小をBへ（ここで小と中がBに揃う）→大をCへ→小をAへ→中をCへ→小をCへ」で完成です。先ほどの再帰の3ステップ（2枚をBへ退避→大をCへ→2枚をCへ）が、そのまま手順に現れていることが確認できます。
また、このパズルは19世紀フランスの数学者エドゥアール・リュカが考案したものとして知られ、「64枚の円盤を僧侶が移し替え終えると世界が終わる」という伝説の演出とともに広まりました。64枚の最小手数は (2^64)-1 回、およそ1,845京回という途方もない数で、指数的な増加の恐ろしさを物語っています。
⚠️ よくある誤解・紛らわしい用語
- 最小手数の式の取り違え — 正しくは「(2^n)-1」です。「2n-1」「n^2-1」「2^(n-1)」などの誤答選択肢と混同しないよう、3枚=7回で検算する癖をつけましょう。
- 「AIの実用問題」ではない — ハノイの塔はあくまで教材・練習問題（トイ・プロブレム）です。現実の複雑な問題がこの方法でそのまま解けるわけではありません。
- 探索木・再帰との関係 — ハノイの塔は探索木で場合分けしても解けますが、教材としての本領は「再帰的に分解すると鮮やかに解ける」ことにあります。両方の文脈で登場し得ます。
- ルールの細部 — 「大きい円盤を小さい円盤の上に置けない」が正しい制約です。逆に書かれた選択肢に注意しましょう。
📝 試験でのポイント
- 「円盤n枚のときの最小手数は？」という計算・式選択の問題が最も想定されます。(2^n)-1 と、n=3で7回になることを押さえましょう。
- 「再帰的なアルゴリズムの教材として用いられるパズル」という説明からハノイの塔を選ばせる出題が考えられます。
- ルール2つ（1回1枚・大は小の上に不可）の正誤判定に備えましょう。
- トイ・プロブレムや組合せ爆発の文脈で、探索・推論の他のキーワードと絡めて問われることがあります。
📚 まとめ
- ハノイの塔は、3本のポールと円盤を使い、「1回1枚」「大を小の上に置けない」のルールで円盤の山を移し替えるパズルです。
- 円盤n枚の最小手数は (2^n)-1 回で、規模とともに手数が指数的に増える組合せ爆発を体感できます。
- 「n枚の問題をn-1枚の問題に分解する」再帰的アルゴリズムの定番教材として、計算機科学・AI分野で重要な役割を果たしてきました。
- 試験では最小手数の式とルールの正確な理解が問われどころです。
