ハノイの塔

3本の柱と大きさの違う円盤を使うパズル

ハノイの塔(Tower of Hanoi)は、3本の柱と、大きさの違う何枚かの円盤を使うパズルです。はじめはすべての円盤が1本の柱に、下から大きい順に積まれています。ルールを守りながらこの山を別の1本の柱へそっくり移せば完成です。1883年、フランスの数学者エドゥアール・リュカ(Édouard Lucas)が考案したとされますが、リュカがどこまで関わったかには異論もあるとされています。

一般に知られているルールは次のとおりです。1つ目に、1回に動かせる円盤は1枚だけです。2つ目に、動かせるのは、どれかの柱のいちばん上にある円盤だけです。3つ目に、ある円盤の上に、それより大きな円盤を置くことはできません。残りの1本の柱は、円盤を一時的に置いておく場所として使えます。

円盤3枚を最小の7手で移す手順

柱を左からA、B、Cと呼び、Aに積まれた小・中・大の3枚をCへ移す場合を追ってみます。

1手目で小をAからCへ、2手目で中をAからBへ動かします。3手目で小をCからBへ動かし、中の上に重ねます。これでAには大だけが残り、Cは空きます。4手目で大をAからCへ動かします。5手目で小をBからAへ、6手目で中をBからCへ動かし、大の上に重ねます。最後に7手目で小をAからCへ動かすと、3枚がCに下から大・中・小の順で並びます。

この手順を見ると、4手目の前半の3手は「小と中の2枚をAからBへ移す」作業、後半の3手は「その2枚をBからCへ移す」作業になっています。2枚の山を移すには3手かかるので、3枚では3手と1手と3手を足した7手になります。

n枚の最小手数が2ⁿ - 1回になる理由

円盤がn枚のときの最小手数をT(n)と書くと、上の手順は一般にも同じ形で説明できます。いちばん大きな円盤は、少なくとも1回は目的の柱へ動かす必要があります。大きな円盤を動かす瞬間には、その上に何も載っておらず、行き先の柱も空いていなければなりません。つまり残りのn - 1枚は、すべて3本目の柱に集まっている必要があります。大きな円盤を動かしたあとは、そのn - 1枚を大きな円盤の上へ移し直します。

したがって、n枚を移す手数は、n - 1枚を移す手数の2回分に、大きな円盤を動かす1手を足したものになります。式で書くと、T(1) = 1、T(n) = 2 × T(n - 1) + 1です。この式を順にたどると、T(2) = 3、T(3) = 7、T(4) = 15となり、一般にT(n) = 2ⁿ - 1が成り立ちます。一般に知られている最小手数の性質は、このように算術で確かめられます。

このように、大きな問題を同じ形をした一回り小さな問題に分けて解く考え方は、再帰と呼ばれます。n枚の問題をn - 1枚の問題2つに分けて解く手順は、プログラムで書くと短い再帰の関数になります。

1枚増えるごとにおよそ2倍になる手数

2ⁿ - 1という式は、円盤が1枚増えるたびに最小手数がおよそ2倍になることを表しています。3枚なら7手、10枚なら1,023手、20枚なら1,048,575手です。64枚になると18,446,744,073,709,551,615手に達します。1秒に1手ずつ休まず動かし続けても、1年を365日として計算すると、終えるまでに約5,849億年かかる数です。

手数の多さとは別に、円盤の置き方が何通りあるかも数えられます。どの円盤も3本の柱のどれかに置かれ、同じ柱の中では大きい順に積むしかないので、置き方は1枚ごとに3通りずつ増え、全部で3ⁿ通りになります。3枚なら27通り、10枚なら59,049通りです。

探索の問題として見たハノイの塔

ハノイの塔は、探索の問題として書き直すことができます。円盤がどの柱にどう積まれているかという置き方の1つ1つが状態で、全部がAに積まれた置き方が初期状態、全部がCに積まれた置き方が目標の状態です。1枚の円盤をルールどおりに動かすことが操作にあたります。どの状態からでも、取れる操作は2通りか3通りしかありません。いちばん小さい円盤は、ほかの2本の柱のどちらにも動かせます。残る2本の柱の間では、上にある円盤の小さいほうを他方へ動かす1通りだけが残るからです。

初期状態から操作を重ねてできる状態の広がりを木の形で書き出したものが探索木です。1手ごとの費用を同じとみなせば、浅い手数の状態から順に調べる幅優先探索で目標の状態に着いた道筋は、最小手数の手順になります。

状態、操作、目標がこのように短く曖昧さなく決まることは、トイ・プロブレムの条件そのものです。ハノイの塔は、円盤の枚数とともに状態の数が増えていく様子について、小さな規模から具体的に数えられる例でもあります。

解き方が分かっていても手数は減らない

ハノイの塔では、最小手数の手順は上の再帰の考え方で先に分かっています。そのため、枚数が増えて困るのは「どう動かせばよいかを見つけること」ではなく、「決まった手順そのものが長くなること」です。64枚の例で手数が天文学的になるのは、探し方が下手だからではなく、答えとなる手順の長さが2ⁿ - 1回だからです。

一方、探索の題材として手順を知らないふりをして探す場合には、調べる状態の数が問題になります。この2つの見方を区別しておくと、トイ・プロブレムとしての使われ方と、パズルとしての性質を混同せずに済みます。

G検定での位置づけ

G検定のシラバスでは、ハノイの塔は中項目3「探索・推論」に属するキーワードの一つです。同じ中項目には、探索木、幅優先探索、深さ優先探索、ブルートフォースなどが並びます。

ハノイの塔は、トイ・プロブレムという分類に当てはまる個別の問題として位置づけられます。トイ・プロブレムは特定のパズルの名前ではなく、ルールを簡潔で厳密に書ける問題をまとめて呼ぶ語です。第1次AIブームの探索と推論の研究では、迷路やパズルのような問題は解けても、記述の定まらない現実の問題は解けないという限界が見えてきたとされます。ハノイの塔は、そうした問題の具体的な姿を思い浮かべるための例になります。