ハノイの塔とは

ハノイの塔は、1883年にフランスの数学者エドゥアール・リュカが考案したパズルです。3本の柱のうち1本に、大きさの違う円盤が下から大きい順に積まれています。次の規則を守り、すべての円盤を別の柱へ移します。

• 1回に動かせるのは、いちばん上の円盤1枚だけ
• 小さい円盤の上に大きい円盤を置いてはいけない

探索問題としての表し方

AIでは、ハノイの塔を探索の例題としてよく使います。円盤の置き方の1通りを「状態」、円盤を1枚動かすことを「操作」とみなすと、初期状態から操作を重ねてゴールに至る手順を探す問題になります。これを木の形に広げたものが探索木です。根に近い順に調べる幅優先探索なら、最初に見つかる解が最短手数の解になります。

円盤の置き方は、各円盤を3本のどの柱に置くかで決まります。同じ柱の円盤の順番は大きさで決まるため、円盤がn枚なら状態は3^n通りです。

最短手数の計算

n枚を移すには、まず上のn-1枚を空いている柱へ移し、いちばん大きい円盤を目的の柱へ1手で動かし、最後にn-1枚をその上へ移します。最短手数をT(n)とすると、T(n) = 2T(n-1) + 1、T(1) = 1です。これを解くとT(n) = 2^n - 1になります。

• 1枚：1手
• 2枚：2×1＋1＝3手
• 3枚：2×3＋1＝7手
• 4枚：2×7＋1＝15手

64枚では2^64 - 1手、つまり約1,845京手です。1秒に1手ずつ動かしても、5,800億年以上かかります。

トイ・プロブレムとしての位置づけ

ハノイの塔は、規則とゴールがはっきりしたトイ・プロブレムの典型です。手法の動きを確かめたり、手法どうしを比べたりするのには向いています。しかし、ここで解けたからといって、現実の複雑な問題が解けることにはなりません。

覚え方

「1枚増えるごとに、手数は2倍＋1」と覚えます。