当サイトを閲覧いただきありがとうございます。 本記事はパズル界の大御所「ハノイの塔」について解説します。
3本の柱と、大きさの異なる円盤。円盤の山を別の柱へ移すだけの単純な遊びですが、このパズルには「64枚の黄金の円盤がすべて移し終わったとき、世界は終わる」という伝説が添えられています。実際に計算すると、64枚の移動には最短でも約1845京手、1秒に1手動かしても約5800億年かかります。宇宙の年齢の40倍以上です。たった3本の柱から天文学的な数が湧き出す仕組み、そこに隠れた再帰という強力な考え方を見ていきます。
ハノイの塔とは
ハノイの塔（英語では Tower of Hanoi）とは、単純な2つのルールから、指数関数的に膨らむ手順が生まれることを体感できるパズルです。ルールを整理しておきます。
・柱が3本あり、左の柱に大きさの異なるn枚の円盤が、大きい順に積まれている ・1回に動かせる円盤は1枚だけ。各柱のいちばん上の円盤しか動かせない ・小さい円盤の上に、それより大きい円盤を置いてはいけない ・すべての円盤を別の柱へ、同じ大小の順で移し終えたら完成
円盤が2枚なら3手、3枚なら7手で解けます。子供でも遊べる難度です。ところが枚数を1枚増やすたびに、必要な手数は倍増よりわずかに多いペースで膨らんでいき、10枚で1,023手、20枚で104万手を超え、64枚では宇宙の寿命を使い果たす規模に達します。この急成長の正体を、後ほど種明かしします。
1883年、数学者リュカの茶目っ気から生まれた
ハノイの塔の出自は、はっきり分かっています。1883年、フランスの数学者エドゥアール・リュカが玩具として発売したものです。リュカは素数の研究で名を残す本職の数学者ですが、この玩具は「シャム（タイ）のン・クラウス教授」という架空の人物の考案として売り出されました。N. Claus（クラウス）は Lucas（リュカ）の綴り替え（アナグラム）で、東洋風の神秘的な演出も含めて、リュカの茶目っ気あふれる仕掛けだったわけです。
冒頭で紹介した64枚の円盤の伝説も、由来はここにあります。「インドの寺院で僧侶たちが64枚の黄金の円盤を移し続けており、完了したとき世界は崩壊する」という物語は、発売翌年の1884年に科学著述家アンリ・ド・パルヴィルが紹介して広まったもので、実在の伝承ではなく、販売促進のための創作と考えられています。シマウマパズルのアインシュタイン伝説と同じく、パズルには魅力的な出自の物語が後付けされがちですが、ハノイの塔の場合は作り話の質まで一級品でした。何しろ「完成に5800億年かかる」という計算の裏付けがあるのですから、世界の終わりの装置としては理想的です。
最小手数が「2のn乗マイナス1」になる仕組み
このパズルの核心は、次のひとことに尽きます。「n枚を移す作業は、n−1枚を移す作業2回と、最大の円盤の移動1回に分解できる」
いちばん下の最大円盤を目的の柱へ動かすには、その上に載っているn−1枚を、いったん空いている柱へ丸ごと退避させるしかありません。最大円盤を動かしたら、退避させたn−1枚をその上へ戻します。つまり手順は必ず「n−1枚の引っ越し→最大の1手→n−1枚の引っ越し」という三部構成になります。
つまり、n枚の最小手数は「n−1枚の最小手数の2倍に、1を足したもの」になります。1枚なら1手なので、順に計算すると3手、7手、15手、31手……と続き、一般に2のn乗−1手になります。枚数が1枚増えるだけで作業量がほぼ2倍になるので、64枚では2の64乗−1、約1845京手という怪物じみた数字に達します。
3枚の場合の7手を実際に並べてみると、構造がよく見えます。
①最小を目的の柱へ ②中を空き柱へ ③最小を中の上へ（ここまでで上2枚の退避が完了） ④最大を目的の柱へ（全体の折り返し点。たった1手） ⑤最小を元の柱へ ⑥中を目的の柱へ ⑦最小を中の上へ（退避した2枚を戻して完成）
前半3手と後半3手が「2枚版の手順」そのものになっており、真ん中に最大の1手が挟まる。分解の説明が、そのまま手順表になっていることが分かると思います。
そして、これより少ない手数では絶対に解けないことも、同じ分解から示せます。最大円盤を動かす瞬間には、残り全部が別の1本の柱に退避済みでなければならない。その退避にも復帰にも、n−1枚版の最小手数が丸ごと必要だからです。解き方と限界の証明が同じ一つの分解から出てくるところが、このパズルの数学的な美しさだと思います。
再帰という考え方の入門書として
「問題を、ひと回り小さい同じ形の問題に帰着させる」この考え方は再帰と呼ばれ、コンピュータ科学の背骨の一つです。ハノイの塔はその最良の教材として、世界中のプログラミング入門書に登場し続けています。
再帰のありがたさは、全体の手順を1手ずつ考えなくてよいことです。7枚のハノイの塔は127手ありますが、覚えるべきは「6枚版を2回と、最大の1手」という分解だけ。6枚版は5枚版の分解に、5枚版は4枚版に……と丸投げが続き、最後は「1枚なら1手」という自明な底に着地します。データの整列で使うクイックソート、フォルダの中を総なめする処理、フラクタル図形の描画など、実用のアルゴリズムの多くがこの「大きな問題を小さな相似形に割る」型でできています。
2進数のリズムと心理検査への広がり
数学の側から眺めると、思わぬ絵柄も隠れています。円盤の動きを最初から並べると、最小の円盤は1手おき、2番目の円盤は4手に1回、3番目は8手に1回と、2進数のカウンタが繰り上がるのとまったく同じリズムで動いていることが分かります。また、あり得る配置すべてを点にして、1手で移り合える配置同士を線で結ぶと、シェルピンスキーの三角形と呼ばれる三角形が入れ子に続くフラクタル図形が浮かび上がります。再帰で作られたパズルの全体地図が、再帰で作られる図形になる。できすぎた話ですが、本当の話です。
ハノイの塔は他の分野にも顔を出します。心理学では、先を読んで計画を立てる力（実行機能）を測る検査課題として使われており、その改良版であるロンドン塔検査は神経心理学の定番になっています。また、バックアップの世代管理には円盤の動きのパターンを流用した「ハノイの塔方式」と呼ばれるローテーションが実在します。1枚の円盤は1手おきに、2枚目は4手おきに動くという規則性が、少ない本数のテープで新旧のバックアップをバランス良く残す仕組みに転用されているのです。19世紀の玩具が、現代のサーバー室で働いているのは愉快な話だと思います。
迷わない動かし方と、柱が4本の世界
最短手順で迷わず動かすコツはありますか？
覚えるべき規則は2つだけです。①最小の円盤を1手おきに動かす。②最小円盤は毎回同じ向きに巡回させる（枚数が奇数なら目的の柱へ向かう向き、偶数なら逆向きに回します）。最小円盤を動かさない番の手は、実は打てる手が1通りしかないので迷いません。この2つを守るだけで、自動的に最短手順をなぞれます。再帰で設計された手順が、こんな単純な反復規則に化けるという事実も、このパズルの隠れた見どころです。
柱が4本になったらどうなりますか？
手数は劇的に減ります。たとえば8枚の場合、3本柱では255手必要ですが、4本柱なら33手で済みます。退避場所が1本増えるだけで、指数の爆発が大幅に緩むわけです。4本柱の最適解は1941年に提案された分割法（フレーム・スチュワートの方法）が長らく「最適らしい」とされてきましたが、厳密に最適だと証明されたのは2014年になってからでした。子供の玩具の完全解明に、現代数学が130年かかったことになります。
64枚の伝説の「5800億年」はどう計算するのですか？
2の64乗−1は18,446,744,073,709,551,615、約1845京手です。1秒に1手のペースで割ると約5849億年となり、宇宙の年齢（約138億年）の40倍以上になります。ちなみにこの2の64乗−1という数は、「チェス盤の64マスに米粒を倍々で置く」という有名な小話に出てくる米粒の総数と同じです。64回の倍々がどれほど恐ろしいかを伝える題材として、ハノイの塔とチェス盤の米は双璧と言えます。
関連する論理クイズ・パズル
布石の一手で時間を最適化する「橋とたいまつの問題」、状態の地図で最短手順を導く「川渡り問題」、そして無限回の操作を考える極限の思考実験「トムソンのランプ」の記事です。
まとめ
本記事は「ハノイの塔」について解説しました。如何だったでしょうか。
3本の柱と2つのルールという極小の世界から、宇宙の寿命を超える時間が立ち上がる。その源は「n枚の問題はn−1枚の問題2回に分解される」という、たった1行の構造でした。この分解を見抜けば、最短手順も、その手数も、これ以上縮まない証明までも一度に手に入ります。
大きすぎて手に負えない仕事に出会ったら、ハノイの塔を思い出してください。「ひと回り小さい同じ形の仕事」が中に隠れていないか。それを見つけた瞬間、127手の迷路は「分解1行」に畳まれます。リュカが玩具に仕込んだこの知恵は、140年経った今もプログラミングの世界で現役です。
論理クイズ・確率パズルの一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：論理クイズ・確率パズル（9/11）
