ハノイの塔の計算機

それは実際どれくらいの長さか

上の数字は正確ですが、それだけではほとんど何も教えてくれません。何十億を超えたあたりから、大きな数はどれも似たように見えます。この計算が本当は何をしているのかは、語るより見るほうが早い。円盤が1枚増えるたびに手数は倍になるので、枚数を等間隔に並べた物差しは、時間では倍々になる物差しになります。そしてコーヒー休憩（10枚、17分）から宇宙の年齢（59枚）までの距離は、およそ50歩しかありません。

• 1枚 — 1手 — 1秒：1秒に初めて届く枚数です。
• 6枚 — 63手 — 1分：1分に初めて届く枚数です。
• 12枚 — 4,095手 — 1時間：1時間に初めて届く枚数です。
• 17枚 — 131,071手 — 1日：1日に初めて届く枚数です。
• 25枚 — 33,554,431手 — 1年：1年に初めて届く枚数です。
• 32枚 — 4,294,967,295手 — 136年：人の一生に初めて届く枚数です。
• 38枚 — 274,877,906,943手 — 8,710年：有史以来のすべての時間に初めて届く枚数です。
• 59枚 — 576,460,752,303,423,487手 — 183億年：宇宙の年齢に初めて届く枚数です。

左寄りの色の付いた範囲が、ここで実際に遊べる全部です。11枚なら長めの一局、25枚なら休みなしで1年ぶん、59枚で宇宙の年齢を超えます。この軸のどこでもルールは何も変わりません。変わるのは数だけです。

式

n枚の完璧な一局はちょうど2ⁿ − 1手です。これがハノイの塔の式で、上付き文字が使えないときは 2^n − 1 とも書きます。これは誰かが達成した最高記録ではなく、証明された下限です。いちばん大きい円盤が動くためには、それより小さい円盤がすべて予備の塔に積まれていなければならず、大きい円盤が渡ったあとは全部がその上に戻らなければなりません。n − 1枚の全体移動が2回と、1手です。

T(n) = 2·T(n − 1) + 1、出発点はT(0) = 0。円盤がなければ手数もゼロです。

1. 1上にあるn−1枚を予備の塔へ移します。それが済むまで、ほかには何もできません。

2. 2いちばん大きい円盤が自由になり、目標の塔も空いています。1手で渡ります。この段階に必要なのはその1手だけです。

3. 3その上にn−1枚を積み直します。1枚少ないだけの同じ問題で、最後は1手で動く円盤1枚にたどり着きます。

これを展開すると 1, 3, 7, 15, 31, 63 となります。どれも前の数の2倍に1を足した数で、2の累乗より1小さい数の並びです。円盤を1枚足すたびに仕事は倍以上になり、だからこのパズルは50歩足らずで、コーヒー休憩から宇宙の年齢より長い時間へと届いてしまいます。

同じ漸化式が、このパズルが情報科学の授業で有名な理由でもあります。円盤ごとに仕事が倍になるので、再帰の解法の実行時間はO(2ⁿ)です。その裏に賢いアルゴリズムが隠れているわけではありません。手数そのものが指数的で、すべての手を出力しなければならないからです。一方でかからないのがメモリです。再帰は1枚ずつ下りていくだけなので、抱えるスタックフレームはO(n)、円盤1枚につき1つと基底の場合の1つだけ。ここでいちばん大きい盤面で16、伝説で65です。詳しい導出と、これがマスター定理を当てはめられる漸化式ではない理由は、アルゴリズムのページにあります。

枚数ごとの最少手数

これがここで遊べる枚数です。難しさの区分は、盤面の枚数調整の横に出るものと同じで、どの枚数からもそれを解く手順の一覧へ行けます。

盤面の外へ

15枚を超えると、このパズルは遊ぶものではなく計算するものになります。数は相変わらず正確です。ただ、人の一生では届かないだけです。

この数には名前がある

2の累乗より1小さい数はメルセンヌ数と呼ばれ、M_n = 2ⁿ − 1 と書きます。つまり上の表の数字はすべてメルセンヌ数で、ハノイの塔の手数がそれ以外になることはありません。メルセンヌ数がたまたま素数であるとき、それはメルセンヌ素数です。記録的な大きさの素数の探索が何十年もこの数の上で走っているのは、2ⁿ − 1 が同じ大きさの適当な数よりずっと安く素数判定できるからです。

M_n が素数になりうるのは n 自身が素数のときだけですが、それだけでは足りません。その反例は、ここで遊べる一局です。11は素数ですが、その2,047手は素数ではありません。2,047 = 23 × 89 だからです。この盤面の枚数のうち、手数が素数になるのは3、5、7、13枚です。OEIS A000225 が全体の数列です。

64枚の伝説

このパズルは1883年に売り出され、1年とたたないうちに物語がつきました。ベナレスの寺院で、僧たちが3本のダイヤモンドの針のあいだで64枚の黄金の円盤を動かしており、最後の1枚が置かれたとき世界が終わる、という話です。計算してみると安心できます。64枚は18,446,744,073,709,551,615手で、1秒に1手なら5,850億年。いまの宇宙の年齢のおよそ40倍です。

よくある質問

ハノイの塔は何手かかりますか？

最少はn枚で 2ⁿ − 1 手です。3枚で7手、5枚で31手、10枚で1,023手、20枚で1,048,575手。円盤が1枚増えるごとに合計は倍を少し超えます。n枚を解くとは、n − 1枚を2回解いて、その間に1手はさむことだからです。

なぜ式が 2ⁿ − 1 なのですか？

n枚を動かすには、まず上のn − 1枚をどかし、次にいちばん大きい円盤を1回動かし、そのn − 1枚をその上に戻さなければなりません。そこから T(n) = 2·T(n−1) + 1、T(1) = 1 が出ます。展開すると 1, 3, 7, 15, 31 となり、どれも前の数の2倍に1を足した数、つまりちょうど 2ⁿ − 1 です。

ハノイの塔の計算量はどれくらいですか？

O(2ⁿ) です。円盤ごとに仕事が倍になるので、再帰の解法は 2ⁿ − 1 手を作ります。これを上回るアルゴリズムはありません。手そのものを出力しなければならず、その数がこれだけあるからです。空間は O(n) だけです。再帰は1枚ずつ下りるので、同時にスタックに載る枠は多くても n + 1 個。64枚の呼び出しは、スタックを使い切るよりずっと早くあなたの忍耐を使い切ります。

64枚だとどれくらいかかりますか？

64枚には18,446,744,073,709,551,615手が必要です。1秒に1手なら5,850億年で、いまの宇宙の年齢よりはるかに長くなります。1884年にこのパズルへ添えられた伝説の狙いは、まさにそこにあります。

2ⁿ − 1 より短い解はありえますか？

ありません。2ⁿ − 1 は「いまのところの最良」ではなく、証明された下限です。いちばん大きい円盤は少なくとも1回動かなければならず、そのためにはより小さい円盤がすべてその上からも行き先からもどいている必要があります。そこから2つの部分移動が必然となり、同じ理屈が下まで繰り返されます。

途中まで解いた盤面にも計算機は使えますか？

このページでは使えません。2ⁿ − 1 は、すべての円盤が1本の塔にある状態を前提にしています。すでに途中まで進んだ配置からの最短解には、どんな正しい配置からでも最適な手順を計算するソルバーを使ってください。 ソルバーを開く →