ハノイの塔のはなし

ハノイの塔は、3本の棒と、大きさの違う円盤で遊ぶパズルです。円盤を1枚ずつ動かして、左の棒の塔を右の棒へ引っ越しさせます。 ルールは「大きい円盤を小さい円盤の上に置かない」だけ。それなのに、円盤が1枚増えるごとに、必要な手数がほぼ2倍になります。

n枚なら、最短は 2ⁿ − 1 手

いちばん大きい円盤を動かすには、その上の塔をぜんぶ別の棒へどかしておく必要があります。どかす作業は「1枚少ない塔の引っ越し」です。 動かしたあと、どかしておいた塔をもう一度その上へ引っ越しさせます。つまり、n枚の手数は「n−1枚の手数を2回」と「大きい円盤の1手」を足したものです。 これを順にたどると、最短は 2ⁿ − 1 手になります。3枚で7手、4枚で15手、5枚で31手、6枚で63手、7枚で127手です。 このサイトの3枚から7枚まで、プログラムで最短の手数を調べ、この式のとおりになることを確かめました。

円盤の数	最短の手数
3	7
4	15
5	31
6	63
7	127

ここから「もしも64枚だったら」を計算してみましょう。2⁶⁴ − 1 手を、1秒に1手のペースで動かし続けると、約5850億年かかります。 宇宙が生まれてからの時間（約138億年）の、およそ42倍です。

箱に添えられた物語

このパズルは、フランスの数学者エドゥアール・リュカが考えて、1883年に売り出したとされています。 そのとき、発売元の名前として「シャム国のN・クロース教授」という名前が使われました。この名前の文字を並べかえると「アミアンのリュカ」になる、と伝えられています。 数学者の遊び心がうかがえる話です。

パズルには、こんな物語が添えられていました。インドのベナレスの寺院で、司祭たちが64枚の金の円盤を1枚ずつ移し替えている。すべて移し終えたとき、世界は終わる、という話です。 これはパズルを売り出すときに添えられた物語で、昔から伝わる本物の伝説だという証拠は見つかっていません。 先ほどの「約5850億年」を思い出すと、世界はまだ当分終わらなさそうです。

「ハノイ」という名前は、ベトナムのハノイにちなんで付けられたとされています。当時のフランス人が、その地域に関心を持っていたことと結びつけて説明されています。

手数を数字で読む

いちばん小さい円盤を「1」、次を「2」…と数えると、動かす円盤は 1, 2, 1, 3, 1, 2, 1, 4, … の順になります。ものさしの目盛りの長さの並びと同じ形です。 m手目に動かす円盤は、「m を2で何回割れるか」で決まります。たとえば4手目なら、4は2回割れるので、3番目に小さい円盤です。

もう一つ。円盤の位置を「状態」と考えて、状態を点、1手で変わる関係を線で結ぶと、大きな図ができます。3枚なら27個の点（3×3×3）です。 円盤を増やすと、この図は同じ形の三角形を3つつないだ形になり、シェルピンスキーの三角形という有名な図形に似てきます。 遊びの裏側に、こんな形がかくれています。作品ページで円盤を3枚にすると、この図の中を自分がどう進んだかを見られます。

解くときの考え方

• いちばん大きい円盤だけを見る。その円盤を動かす前に、上の塔を「行き先ではない棒」に集めておきます。
• 小さい塔の引っ越しは、同じやり方のくりかえし。円盤が何枚あっても、やることは「ひとつ小さい塔を動かす」です。
• いちばん小さい円盤は、1手おきに動かす。1, 2, 1, 3, 1, 2, … の並びを思い出すと、小さい円盤が1手おきに登場します。
• 途中で止まっても大丈夫。どんな局面からでも、そこから最短の手順があります。

行き詰まったら、作品ページの「ヒント」で次の1手を見られます。「自動で解く」では、最短の手順を最後まで再生します。