ハノイの塔(1883) — 再帰という遺産を遺した、終わらない64枚

はじめに

これは1883年の玩具である。三本の杭が立ち、その一本に大きさの異なる円盤が、下ほど大きく順に積まれている。規則はわずか二つ——円盤は一度に一枚しか動かせず、小さい円盤の上に大きい円盤を置いてはならない。この縛りのもとで、塔をまるごと別の杭へ移し替えよ。それだけの遊びが、いまも「ハノイの塔」の名で世界中の教室と玩具箱に残っている。

見た目はまったく素朴だ。木の杭と数枚の輪。子どもでも規則は一分で覚えられる。だが私がこの玩具を歴史の対象として取り上げるのは、その素朴さの裏に、後の計算機科学が「再帰」と呼ぶことになる構造が、すでに完成形で埋め込まれていたからである。1883年の段階で、人はこの構造を指で触れる玩具として手にしていた。

本稿では、この塔を発明した数学者の正体と、彼がまとわせた壮大な作り話、そして単純な規則から導かれる 2ⁿ−1 という数の重みを辿る。懐古のためではない。現代のパズルが当たり前のように使う「入れ子」「状態空間」という発想が、どれほど古い場所から来ているのかを確かめるためである。

三本の杭と黄金の塔——1883年の玩具（イメージ・AI生成）

その時代の文脈

1883年のパリ。発明者は数学者エドゥアール・リュカ(Édouard Lucas, 1842–1891)である。だが玩具が世に出たとき、その作者名は「N. Claus (de Siam)、Li-Sou-Stian 学院教授」と記されていた。これは目くらましだった。「N. Claus (de Siam)」は「Lucas (d'Amiens)」のアナグラムであり、「Li-Sou-Stian」は彼が当時教えていたパリの名門校 Lycée Saint-Louis(サン=ルイ高等中学)の綴り替えである。この仕掛けは科学評論家アンリ・ド・パルヴィル(Henri de Parville)によって早々に見破られた。

リュカは余技で玩具を作ったわけではない。彼は数論の本格的な研究者で、後世に「リュカ数列」「リュカ–レーマー判定法」の名を残した人物である。当時のヨーロッパには『récréations mathématiques(数学的レクリエーション)』という、遊びを通じて数の性質を伝える豊かな伝統があり、ハノイの塔はその系譜のなかに置かれた一品だった。リュカ自身の同名の著作にも、この塔は収められている。

玩具には壮大な物語が添えられていた。曰く、インドのベナレス(現ヴァラナシ)の寺院で、僧たちが三本のダイヤモンドの針の上で64枚の黄金円盤を同じ規則で移し続けており、その塔が完成したとき世界は崩れて終わる、と。むろん作り話である。だが私はこの脚色を軽んじない。数の冷たさに神話の重みを与えるこの手つきこそ、後年のパズル作家たちが繰り返し学ぶ「演出」の原型だからだ。

卓上の箱と偽名の紙片——時代背景（イメージ・AI生成）

メカニクス

規則は1883年から変わらない。円盤は一度に一枚。大きい円盤を小さい円盤の上に載せてはならない。空いた杭は自由に使ってよい。この三点だけで、塔の移動という課題が定義される。手で触れれば数分で「なんとなく動かせる」が、最短手数を意識した途端、構造が立ち上がってくる。

その構造とは再帰である。n枚の塔をAからCへ移したい。ならば、上のn−1枚をいったんBへ退避させ、最大の一枚をAからCへ移し、最後にBに退避したn−1枚をCへ移せばよい。問題が、ひと回り小さい同じ問題二つに分解される。手数T(n)はT(n)=2·T(n−1)+1という関係を満たし、これを解けばちょうどT(n)=2ⁿ−1となる。1枚なら1手、3枚なら7手、10枚なら1023手。最短解は一意ではないが、最短手数はこの式で完全に決まる。

ここで例の伝説に戻る。64枚なら2⁶⁴−1、すなわち約1844京手だ。仮に僧が一秒に一手を休まず動かし続けても、約5850億年を要する——現在見積もられている宇宙の年齢のおよそ42倍である。世界が終わるまで塔は完成しない、という脅し文句は、つまり指数関数の途方もなさを神話の言葉に翻訳したものだった。単純な規則から爆発的な数が生まれる。この落差こそ、思考系パズルが今も売り物にしている快感の核である。

再帰の分解と、2ⁿ−1 という帰結（イメージ・AI生成）

現代への系譜

1883年の玩具が最も深く根を張った先は、20世紀の計算機科学だった。ハノイの塔は、プログラミング教育で再帰を教えるときのほぼ標準的な題材になっている。「自分自身をひと回り小さくして呼び出す」という再帰の発想を、これほど短い規則で完璧に体現する例はそうない。同時にこの塔は、すべての盤面を点、合法手を辺と見なす『状態空間』という見方の、最も分かりやすい教材でもある。

私はこの「状態空間」という視点を、現代のパズルを読むための鍵だと考えている。盤面の全体を一つの巨大な迷路と捉え、その中を最短で辿る——倉庫番の解析も、スライドパズルの可解性も、この見方の上に立っている。ハノイの塔が1883年に与えたのは、玩具そのものというより、思考系パズルをこう眺めればよいという一つの眼鏡だった。

入れ子の構造を真正面から遊びにした現代の例として、私は2022年にSteamで出た『Patrick's Parabox』を系譜の延長線上に置いて読む。箱の中に箱があり、その箱が自分自身を含みうる——これは再帰そのものをルールに据えたパズルだ。むろん作者がハノイの塔から直接着想したと証言しているわけではない。だが「小さくした同じ問題が入れ子になる」という骨格は、1883年の木の塔がすでに手で触れる形で示していたものである。系譜とは、影響の証文ではなく、同じ骨格が時代を越えて反復することだ。

黄金の塔から入れ子の現代へ（イメージ・AI生成）

参考文献

本記事で参照した情報源:

・Wikipedia: Tower of Hanoi

・Wikipedia（日本語）: ハノイの塔

・Wikipedia: Édouard Lucas

・College of William & Mary: The Tower of Hanoi

・Scientific American: The Tower of Hanoi

おわりに

ベナレスの塔は、伝説のなかでまだ動き続けている。5850億年の彼方にある最後の一手は、当然ながら一度も置かれていない。だが、その終わらなさこそが、この玩具が1883年に示したものの本質だと私は思う。単純な規則と、そこから指数的に膨れ上がる手数。手で触れられる有限の道具のなかに、人の一生では辿りきれない無限が畳み込まれている。

歴史的に見て、ハノイの塔が遺したのは個別の解法ではない。問題を自分自身の小さな複製へと分解できるという、再帰の発想そのものだ。それは計算機科学の教科書に移り住み、状態空間という眼鏡となって、いまも新しいパズルを照らし続けている。1883年の木の杭に積まれた数枚の輪は、思考の道具がどれほど古い源を持つかを、静かに思い出させてくれる。

ベナレスの夜、まだ動き続ける塔（イメージ・AI生成）