暇つぶしのために、ハノイの塔をブラウザで作った話

世界が終わるまで続くパズル、ハノイの塔

昔のパズルを、少しずつブラウザで遊べるようにしておきたいと思っています。
大きな目的があるというより、あとで自分が暇なときに遊べる場所を作っておきたい、くらいの気持ちです。
ただ、せっかく作るなら、パズルだけ置いて終わりにするのも少しもったいない気がします。

そのパズルがどこから来たのか。
どんな話がついているのか。
なぜ今でも残っているのか。

そのあたりも一緒に調べておくと、あとで遊ぶときに少し見え方が変わる気がします。

今回作ったのは、ハノイの塔です。

三本の棒と、大きさの違う円盤だけでできたパズルです。
最初は、すべての円盤が左の棒に積まれています。大きい円盤が下にあり、その上に少し小さい円盤が乗り、さらにその上に小さい円盤が乗る。名前の通り、塔のような形になっています。

目的は、その塔を右の棒へ移すことです。
動かせる円盤は、一度に一枚だけ。
小さい円盤の上に、大きい円盤を置くことはできない。
ルールはとても短いです。

でも、このパズルには妙に大きな伝説がついています。

そういう話です。
世界の終わりにしては、作業が地味です。
ただ円盤を一枚ずつ動かしているだけです。
けれど、この「一枚ずつ」が六十四枚まで増えると、確かに途方もない時間がかかるようです。

今回は、そのハノイの塔をブラウザ上で遊べるようにしてみました。

ハノイなのに、ベナレスの話

ハノイの塔という名前を聞くと、ベトナムのハノイを思い浮かべます。
ところが、このパズルに添えられた伝説の舞台はインドのベナレス（現在のヴァーラーナシー）です。

なぜ、ハノイなのにベナレスなのでしょうか。

調べてみると、この名前の混乱こそが、作者の狙いだったことが分かります。

このパズルは、1883年にフランスの数学者エドゥアール・リュカによって発表されました。つまり、古代の寺院から見つかったものではなく、19世紀フランスで作られた「新作パズル」だったのです。

ただ、その売り出し方が非常に凝っていました。
当時のパッケージには、作者として「シャム（タイ）の N. Claus 教授」という名前が記され、「トンキン（ベトナム北部）から持ち帰られた」というエピソードが添えられていました。

地名がバラバラなのには理由があります。
実は、作者の「N. Claus de Siam」という名前は、リュカの本名と出身地である「Lucas d’Amiens」の綴りを並べ替えたアナグラム（文字の入れ替え）です。さらに、教授の所属先とされる学校名までもが、リュカの勤務先の学校名をもじったものでした。

リュカは、単に「数学パズルです」と出すのではなく、架空の教授やアジアの地名をちりばめることで、異国情緒あふれる「神秘のパズル」という設定を作り上げたのです。今の感覚でいうと、世界観まで含めてデザインされた「設定込みの商品」だったと言えます。

三本の棒と円盤という素朴な道具に、「ベナレスの寺院」「世界の終わり」という壮大な物語が重なる。このギャップこそが、ハノイの塔をただの数学パズル以上の存在にしているのだと思います。

ハノイの塔は、ルールだけでなく、売り出し方までよくできています。

一枚増えるだけで、倍になっていく

ハノイの塔の面白さは、手数の増え方にあります。
円盤が一枚なら、一手で終わります。
二枚なら三手。
三枚なら七手。
四枚なら十五手。
五枚なら三十一手。

一枚増えるたびに、ほとんど倍になります。
なぜそうなるのかは、いちばん大きい円盤を動かそうとすると分かります。たとえば五枚の塔を考えます。

いちばん下にある大きな円盤を右の棒へ移したい。
でも、その上には四枚の円盤が乗っています。
まず、その四枚をどこかへどかさなければいけません。
四枚を別の棒へ移す。
ようやく、いちばん大きい円盤を右へ動かす。
そのあと、どかしておいた四枚をまた上に戻す。
つまり、五枚の問題を解くには、四枚の問題を二回解くような形になります。
前の枚数の作業を二回やって、最後に大きい円盤を一回動かす。
だから、手数は
前の手数 × 2 + 1
で増えていきます。

これを続けていくと、円盤が n 枚のときの最短手数は、
2^n - 1
になります。

ここで、伝説に出てくる六十四枚を考えます。
64枚なら、
2^64 - 1
です。

計算すると、
18,446,744,073,709,551,615手。
急に、数字の見た目がおかしくなります。

一秒に一手ずつ動かしても、終わるまでに約5845億年かかるそうです。
世界の年齢が約138億年と言われることを考えると、六十四枚の塔は、ただ長いというより、時間の桁が違います。

もちろん、本当に寺院で僧侶が黄金の円盤を動かしているわけではないでしょう。
でも、話を支えている数の増え方は本物です。

作り話のような伝説と、ちゃんと計算できる途方もない数字が重なっている。
ここが、ハノイの塔の強いところだと思います。

実際に遊ぶと、かなり迷う

ハノイの塔は、ルールだけならすぐ分かります。

一枚ずつ動かす。
大きい円盤を小さい円盤の上に置かない。
全部を右へ移す。

これだけです。
でも、実際に遊ぶと思ったより迷います。
大きい円盤を動かすために、小さい円盤をどかす。
どかした円盤を置くために、また別の円盤を動かす。
そのうち、自分が何の準備をしていたのか分からなくなります。

三枚なら、まだ見えます。
五枚になると、少し手順を考える必要があります。
八枚になると、最短でも二百五十五手です。

八枚くらいなら大したことないように見えますが、実際にやるとけっこう長いです。
一手一手は単純なのに、全体で見ると遠い。

何をすればいいかは分かる。
でも、どう進めれば無駄がないのかは、少し考えないと分からない。
この距離感が、ハノイの塔らしい気がします。

おわりに

実際に作ってみて感じたのは、ハノイの塔は「ギャップ」のパズルだということです。
仕組みは、三本の棒と円盤だけ。
でも、その背後には19世紀フランスの数学者が仕掛けた壮大な「設定」があり、さらにその奥には、人類の歴史を遥かに超える「数字」が控えています。
小さな木製パズルのように見えて、実は底が知れない。 暇なときに少し触るだけなら三枚で十分です。
少し考えたいなら五枚。
八枚は、思ったより長いです。 ぜひ、この「設定」と「数字」の重みを感じながら、一枚ずつ動かしてみてください。
実際に遊べる版はこちらです。

参考文献・出典

[1] ETH Library, “Tower of Hanoi”
https://library.ethz.ch/en/collections-and-archives/platforms/virtual-exhibitions/Its-all-math-and-games/tower-of-hanoi.html

[2] Puzzle Museum, “Eduardo Lucas: La Tour D'Hanoi”
https://www.puzzlemuseum.com/month/picm07/2007-03_hanoi.htm

[3] Wolfram MathWorld, “Tower of Hanoi”
https://mathworld.wolfram.com/TowerofHanoi.html

[4] Maths Careers, “Tower of Hanoi”
https://www.mathscareers.org.uk/tower-of-hanoi/