スマートフォン・タブレット：塔をタップすると一番上の円盤を持ち上げ、別の塔をタップすると置きます。
マウス：円盤をドラッグするか、塔をクリックしてから別の塔をクリックします。
キーボード：← と → で塔を選び、↑ で持ち上げ、↓ で置きます。1・2・3 で塔A・B・Cへ直接移動でき、Esc で円盤を戻します。

間違えても大丈夫です。戻すで直前の手を取り消し、リセットで同じ枚数を最初からやり直せます。ヒントは最短の解法が次に動かす円盤を持ち上げ、行き先を教えてくれます。1手進むならその手を代わりに指します。見ていたいだけなら、自動で解くが最初からだけでなく、盤面が今どの状態でもそこから最後まで解きます。

最初の一手を指すまで、何も数えません。一手目のあと、パネルには次のものが表示されます。

手数、タイマー、そして効率スコア（完璧なゲームに対するあなたのゲームの割合）。
まだ最短手順どおりか、それとも何手外れているか。

盤面の下のタイムラインは、ゲームの全体を記録します。どの時点の配置にも戻れますし、0.5×・1×・2×・4× で再生もできます。この速度は「自動で解く」の速さにも使われます。集中モードでは塔以外がすべて消え、ページは前回遊んだ円盤の枚数を覚えています。クリアすると、結果画面があなたの手数を最少手数と比べ、円盤を1枚増やした挑戦を勧めます。

ハノイの塔というパズル

ハノイの塔は、3本の塔と、そのうち1本に積まれた大きさの違う円盤の山から始まります。一番下が一番大きな円盤です。目的は、次の3つのルールを守って、山をまるごと別の塔へ移すことです。

一度に動かせる円盤は1枚だけ。
動かせるのは、塔の一番上にある円盤だけ。
小さな円盤の上に大きな円盤を置いてはいけない。

パズルはこれで全部で、1分ほどで覚えられます。難しくしているのは3つ目のルールです。下の円盤を動かしている間、上の円盤はどこか置いてよい場所で待たなければならず、塔が3本しかないので余裕はほとんどありません。ハノイの塔の遊び方では、ルールを図で示し、練習用の盤面と実例も用意しています。

このパズルはフランスの数学者エドゥアール・リュカが1883年に発表しました。その翌年、パズルを紹介した雑誌記事が、今では有名な伝説を付け加えました。バラモンの僧たちが64枚の黄金の円盤を移し終えたとき、世界は終わるというのです。1秒に1手のペースなら、それには約5850億年かかります。

最少手数と 2ⁿ − 1 の公式

円盤が n 枚のハノイの塔の最少手数は 2ⁿ − 1 で、2^n − 1 と書かれることもあります。3枚なら7手、4枚なら15手、5枚なら最少で31手です。これは記録ではなく証明された下限で、どの枚数でもこれより短い解はありません。盤面の効率スコアも、この数とあなたの手数を比べています。

公式のもとになる式

この式はルールからそのまま出てきます。一番大きな円盤を動かす前に、その上の n − 1 枚を予備の塔に積んでおく必要があります。次に大きな円盤が移り、最後にその n − 1 枚を上に戻します。これをすべて行う最少手数を T(n) と書くと、

T(n) = 2·T(n − 1) + 1、ただし T(0) = 0（円盤がなければ手数もゼロ）。

各枚数の手数は、1枚少ないときの2倍に1を足したものです。1、3、7、15、31、63。どれも2のべき乗から1を引いた数で、ここから閉じた形 T(n) = 2ⁿ − 1 が得られます。2ⁿ − 1 が最少であることの証明では、この主張の2つの半分（その手数で必ず足りること、それより少なくはできないこと）を順に説明しています。最少手数の計算機を使えば、64枚までどの枚数でも正確な手数がわかります。

円盤の枚数ごとの最少手数

円盤の枚数	最少手数
3 枚	7
4 枚	15
5 枚	31
6 枚	63
7 枚	127
8 枚	255
9 枚	511
10 枚	1,023

各枚数から、すべての手を一覧にして盤面で再生する完全な解答ページへ移れます。ここで遊べる最大は15枚、つまり32,767手です。円盤を1枚増やすごとに、ゲームの長さは2倍に1手を足した長さになります。

ハノイの塔のアルゴリズムと再帰

上の式は、そのままアルゴリズムでもあります。手順として読むとこうなります。n 枚の円盤を出発の塔から目的の塔へ移すには、

n − 1 枚を出発の塔から予備の塔へ移す。
一番大きな円盤を出発の塔から目的の塔へ移す。
n − 1 枚を予備の塔から目的の塔へ移す。

手順1と3は、円盤が1枚少ないだけの同じ問題です。そこでアルゴリズムは自分自身を呼び出してそれを解き、動かす円盤がなくなった呼び出しは何もせずに戻ります。これがハノイの塔の再帰のすべてであり、ほとんどのプログラミングの授業がこのパズルで再帰を教える理由です。コツは、すべての手を一度に思い浮かべようとしないこと。小さいほうの呼び出しが仕事をこなすと信じれば、3つの手順だけで解法は完成です。

このアルゴリズムはちょうど 2ⁿ − 1 手を指すので、実行時間は O(2ⁿ) です。どの手も必ず指さなければならないので、これより速くはできません。一方、使うメモリは O(n) だけです。ハノイの塔のアルゴリズムのページでは、動く盤面の横でコードを1行ずつ実行し、呼び出しの木を描いていきます。また反復による解法は、2つのルールとループだけで同じ手順を生み出します。

Python・Java などで書くハノイの塔

3つの手順は、ほぼそのままコードになります。Python によるハノイの塔は7行の関数で、円盤0枚の基底ケース、2回の再帰呼び出し、そしてその間で手を出力する1行だけでできています。Java によるハノイの塔はクラスの中に同じメソッドを置いたもので、64枚の手数がなぜ long に収まらないのかもわかります。ほかに C、C++、C#、JavaScript の完全なプログラムもあります。

どのコードも実際に実行し、その出力をこのサイトのソルバーと照合済みです。それぞれに、文法の説明ではなく「なぜその行があるのか」を解説する行ごとの説明がついています。

ほかの遊び方・学び方

3本の塔と積み上がった山が簡単に感じられたら、次のものも試してみてください。

デイリーチャレンジ — 全員に同じ、ばらばらの配置がひとつ。協定世界時の午前0時に新しくなります。ソルバーを使わずに解いて連続記録を伸ばしましょう。
ソルバー — どの正しい配置からでも、最短解のすべての手を表示します。この盤面で行き詰まっている配置からも使えます。
攻略法 — どの枚数にも共通するただひとつの考え方と、先を読まずに次の一手がわかるルール。
バリエーション — 3本ではなく4本の塔、円盤が一方向にしか進めない輪、2色の仕分け、ランダムな初期配置。
先生方へ — 45分の授業案、解答つきの印刷用ワークシート、授業ページに埋め込める盤面。

よくある質問

ハノイの塔とは何ですか？

ハノイの塔は、3本の塔と大きさの違う円盤の山を使うパズルです。山をまるごと別の塔へ移しますが、一度に動かせるのは1枚だけで、小さな円盤の上に大きな円盤を置くことはできません。フランスの数学者エドゥアール・リュカが1883年に発表しました。

ハノイの塔を無料でオンラインで遊べますか？

はい。このページの盤面は無料で、スマートフォン、タブレット、パソコンのどの最新ブラウザでも動き、ダウンロードもアカウントも不要です。前回遊んだ円盤の枚数と自己最高記録は、サーバーではなくあなたのブラウザに保存されます。

ハノイの塔の最少手数はいくつですか？

円盤 n 枚の完璧なゲームは 2ⁿ − 1 手です。3枚なら7手、5枚なら31手、15枚なら32,767手です。これより短い解は存在しないので、この数は目標ではなく絶対的な下限です。

ハノイの塔はどうやって解くのですか？

どの解法も同じ考え方の繰り返しです。n 枚の山を目的の塔へ移すには、まず上の n − 1 枚を予備の塔へどかし、一番大きな円盤を移してから、その n − 1 枚を上に戻します。小さい山もまったく同じルールに従うので、ひとつの方法でどの枚数も解けます。

次の一手がすぐわかる近道はありますか？

あります。奇数手目には、一番小さい円盤を決まった向きに塔1つ分動かします。円盤が奇数枚なら左、偶数枚なら右で、端まで行ったら反対側に回ります。つまり3枚のときは、最初の一手で A から C へ回り込みます。偶数手目には、一番小さい円盤に触れない唯一の正しい手を指します。この2つを交互に繰り返すだけで、何も考えずに完璧なゲームになります。

ここでは何枚の円盤で遊べますか？

3枚から15枚までです。まずは3枚で解き方の形をつかみ、そこから1枚ずつ増やしていきましょう。1枚増えるごとに、手間はおよそ2倍になります。

手を戻したり、ゲームを見返したりできますか？

できます。戻すボタンがあるほか、どのゲームにも完全なタイムラインが残ります。前の時点に戻ると盤面はそのときの状態をそのまま表示し、4段階の速度で再生すれば、どこで最短手順から外れたかを確認できます。