ハノイの塔とは？ルール・解き方・最小回数を初心者向けに解説

ハノイの塔とは？ルール・解き方・最小回数を初心者向けに解説

ハノイの塔とは？基本の仕組み

ハノイの塔は、左、中央、右の3本の棒と、中心に穴の開いた円盤で構成されます。最初は、左端の棒にすべての円盤が積まれています。このとき、下に大きい円盤、上に小さい円盤が来るように並びます。

目的は、左端の棒にある円盤を、同じ順序を保ったまま右端の棒へ移すことです。円盤を一枚ずつ動かすだけなので見た目は単純ですが、「大きい円盤を小さい円盤の上に置けない」という制約があるため、先の手順を考えないとすぐに行き詰まります。

AIやアルゴリズムの文脈では、ハノイの塔は「現在の配置からゴールの配置へ、どの手を選べばよいか」を考える問題として扱えます。つまり、パズルの状態を観察し、可能な移動を選び、ゴールまでの道筋を探す練習になります。

歴史と名前の由来

「ハノイの塔」という名前は、パズルの発祥地をそのまま示しているわけではありません。一般には、フランスの数学者エドゥアール・リュカが1883年に考案したパズルとして知られています。

リュカはこのパズルに物語性のある名前を与えました。そのため、ハノイという地名が入っていても、実際の地理的な起源よりも、数学的な遊びとして広まった名称だと考えると理解しやすいでしょう。

現在では、数学、プログラミング、認知課題、教育用パズルなど、幅広い分野で使われています。特に、少ないルールから複雑な手順が生まれる点が、アルゴリズム学習に向いています。

遊び方と守るべきルール

ハノイの塔で守るルールは、大きく分けて2つです。1つ目は、一度に動かせる円盤は1枚だけということです。複数の円盤をまとめて持ち上げたり、2枚を同時に別の棒へ動かしたりすることはできません。

2つ目は、小さい円盤の上に大きい円盤を置いてはいけないということです。どの棒でも、下にある円盤ほど大きく、上にある円盤ほど小さい状態を保つ必要があります。

この2つのルールを守りながら、左端の棒から右端の棒へすべての円盤を移します。中央の棒は、途中で円盤を一時的に置くための補助として使います。最短手順を目指す場合は、目先の移動だけでなく、最終的に大きな円盤を動かす場所を空けることが重要です。

最小移動回数と計算式

ハノイの塔を最短で解くために必要な移動回数は、円盤の枚数で決まります。円盤の枚数を \(n\) とすると、最小移動回数は次の式で表されます。

\(2^n – 1\)

たとえば円盤が3枚なら、\(2^3 – 1 = 7\) なので、最短で7回の移動が必要です。4枚なら \(2^4 – 1 = 15\)、5枚なら \(2^5 – 1 = 31\) になります。

この式から分かるように、円盤が1枚増えるだけで手数はほぼ2倍になります。少ない枚数では直感で解けても、枚数が増えると手順を整理して考える必要があります。ここに、ハノイの塔がアルゴリズム学習に使われる理由があります。

解き方の考え方：再帰で分けて考える

ハノイの塔の解き方は、再帰の考え方で整理すると分かりやすくなります。再帰とは、大きな問題を同じ形の小さな問題に分けて解く考え方です。プログラミングでは、関数が自分自身を呼び出す処理として表現されます。

円盤が \(n\) 枚ある場合、基本の流れは3段階です。まず、上にある \(n-1\) 枚を補助の棒へ移します。次に、一番下の最大円盤を目的の棒へ移します。最後に、補助の棒へ退避していた \(n-1\) 枚を目的の棒へ移します。

この手順は、円盤が3枚でも5枚でも同じ構造です。違うのは、同じ作業を何段階まで繰り返すかです。ハノイの塔が再帰の教材として優れているのは、「自分より小さい同じ問題を先に解く」という考え方が目で追いやすいからです。

AI・探索アルゴリズムとの関係

AIの探索アルゴリズムでは、問題を「状態」「行動」「ゴール」に分けて考えることがあります。ハノイの塔なら、円盤がどの棒に積まれているかが状態、円盤を1枚動かすことが行動、すべての円盤が右端の棒に移った状態がゴールです。

AIにこの問題を解かせる場合、次に選べる合法手を列挙し、その手を選んだ後の状態を調べます。行き止まりや無駄な戻りを避けながら、ゴールへ向かう手順を探すわけです。この考え方は、経路探索、ゲームAI、計画問題などにもつながります。

ただし、ハノイの塔そのものはルールが完全に決まった小さな問題です。実務のAIでは不確実な情報や大量の選択肢を扱うことも多いため、ハノイの塔はあくまで探索の基礎を理解するための入口と考えるとよいでしょう。

プログラミング学習で役立つ理由

ハノイの塔は、プログラミング学習でもよく使われます。特に、再帰呼び出しを学ぶときに、関数がどの順番で呼び出され、どの順番で処理を終えるのかを理解しやすい題材です。

たとえば「3枚の円盤を左から右へ移す」という問題は、「上の2枚を中央へ移す」「一番下を右へ移す」「中央の2枚を右へ移す」という小さな問題に分けられます。この分解をプログラムにすると、円盤の枚数が増えても同じ関数で処理できます。

学習時は、いきなりコードだけを見るよりも、実際の円盤の移動や図と対応させると理解しやすくなります。プログラムが出力する手順を見ながら円盤を動かすと、再帰が単なる文法ではなく、問題を分割する考え方だと分かります。

思考力を鍛える練習としての使い方

ハノイの塔は、子どもから大人まで論理的思考を鍛える教材として使えます。重要なのは、ただ円盤を動かすのではなく、なぜその手を選んだのかを振り返ることです。

最初は3枚から始めるとよいでしょう。3枚なら最短7回で解けるため、手順を紙に書いたり、実物を動かしたりしながら全体像を確認できます。慣れてきたら4枚、5枚へ増やすと、先読みの負荷が上がります。

失敗したときは、どの時点で大きな円盤を動かす場所がなくなったのかを確認します。成功したときは、同じ状態を行き来する無駄な移動がなかったかを見直します。この振り返りが、問題解決力を伸ばす練習になります。

代表的なバリエーション

基本形のハノイの塔は3本の棒を使いますが、さまざまなバリエーションがあります。もっとも分かりやすいのは、円盤の枚数を増やす方法です。枚数が増えると最小移動回数が急増するため、同じルールでも難易度が大きく変わります。

棒の本数を4本以上に増やすバリエーションもあります。棒が増えると選択肢が増えるため簡単に見えるかもしれませんが、最短手順の考え方は基本形と異なります。どの棒を一時退避に使うかが新しい課題になります。

ほかにも、隣り合った棒にしか移動できない、特定の円盤に追加ルールを設ける、といった制限付きのハノイの塔があります。制限を変えると、同じパズルでも探索の性質が変わるため、アルゴリズムの比較にも使えます。

初心者がつまずきやすい注意点

初心者がよくつまずくのは、「一番下の大きな円盤をいつ動かすか」を意識しないまま進めてしまう点です。最大円盤を動かすには、その上にある円盤をすべて別の棒へ退避させる必要があります。目先の小さい円盤だけを動かしていると、退避場所がなくなります。

また、最小移動回数の式を覚えるだけでは、実際の解き方は身につきません。\(2^n – 1\) は必要な回数を示す式であり、どの順番で動かすかは再帰の考え方で整理する必要があります。

AIやプログラミングと関連づけて学ぶ場合は、「正解手順を暗記する」よりも「どの状態からどの状態へ進むのか」を観察することが大切です。状態の変化を追うと、探索アルゴリズムや再帰処理の理解につながります。

まとめ

ハノイの塔は、3本の棒と複数の円盤だけで構成されるシンプルなパズルです。しかし、最小移動回数は \(2^n – 1\) で増えていくため、円盤の枚数が増えるほど手順は急速に複雑になります。

このパズルは、遊びとして楽しめるだけでなく、再帰、探索アルゴリズム、論理的思考、プログラミング学習を理解するための良い入口になります。まずは3枚の円盤で試し、手順を言葉や図にしながら、どのように問題を小さく分けているのかを確認してみましょう。

更新履歴