ハノイの塔とは？パズルのルールから再帰的アルゴリズムまで徹底解説

ハノイの塔（Tower of Hanoi）は、3本の杭と大きさの異なる複数の円盤を使ったパズルです。 もともとはフランスの数学者エドゥアール・リュカが1883年に考案したもので、「バラモンの塔」や「ルーカスタワー」とも呼ばれます。

ルールは非常にシンプルですが、円盤の数が増えると解くための手順が急激に増える奥深さを持っています。 そのため、パズルとしてだけでなく、コンピュータサイエンスの世界では「再帰」という重要なアルゴリズムの考え方を学ぶための典型的な問題として広く知られています。

パズルの目的は、ある杭に積まれた全ての円盤を、決められたルールに従って別の杭に移動させることです。 具体的なルールは以下の通りです。

• 3本の杭と、中央に穴の開いた大きさの異なる円盤が複数枚あります。
• 最初は、すべての円盤が1本の杭に、大きいものが下になるように積まれています。
• 一度に1枚の円盤しか動かすことはできません。
• 小さい円盤の上に大きい円盤を置くことはできません。

これらのルールを守りながら、すべての円盤を元の杭から目標の杭へ移動させればクリアとなります。

ハノイの塔は、その解法が「再帰」というアルゴリズムの構造を持つことから、プログラミングの教材として非常に有名です。 再帰とは、ある問題を解くために、その問題と同じ構造を持つより小さな問題に分割して解いていく手法です。

例えば、「n個の円盤をAの杭からCの杭へ移動させる」という問題を考えてみましょう。この問題は、以下の3つのステップに分解できます。

1. ステップ1: まず、一番大きい円盤（n番目）以外の「n-1個の円盤」を、Aの杭からBの杭（作業用の杭）へ移動させます。
2. ステップ2: 次に、Aの杭に残った一番大きい円盤を、目的地のCの杭へ移動させます。
3. ステップ3: 最後に、Bの杭にある「n-1個の円盤」を、Cの杭へ移動させます。

ここで重要なのは、ステップ1とステップ3が、元の問題（n個の円盤の移動）と同じ構造で、より円盤の数が少ない問題（n-1個の円盤の移動）になっている点です。 このように自分自身をより小さな形で呼び出すことで、複雑な問題をシンプルに解くことができます。

この再帰的な考え方を使うと、Pythonでハノイの塔を解くプログラムを驚くほどシンプルに記述できます。

def hanoi(n, source, destination, auxiliary): """ ハノイの塔を解くための再帰関数 :param n: 円盤の数 :param source: 出発元の杭 :param destination: 目的地の杭 :param auxiliary: 作業用の杭 """ if n > 0: # ステップ1: n-1個の円盤を 出発元(source) から 作業用(auxiliary) へ移動 hanoi(n - 1, source, auxiliary, destination) # ステップ2: n番目の円盤を 出発元(source) から 目的地(destination) へ移動 print(f"{n}番目の円盤を {source} から {destination} へ移動") # ステップ3: n-1個の円盤を 作業用(auxiliary) から 目的地(destination) へ移動 hanoi(n - 1, auxiliary, destination, source)
# 円盤が3枚の場合の実行例
num_disks = 3
hanoi(num_disks, 'A', 'C', 'B') 

ハノイの塔を解くための最小手数は、円盤の数をnとすると 2ⁿ – 1 回となります。 この数式からわかるように、円盤の数が1つ増えるだけで、必要な手数は約2倍になります。

ハノイの塔には、その壮大な計算量にまつわる有名な伝説があります。

インドのベナレスという聖なる都に、世界の中心を示す寺院がありました。そこには3本のダイヤモンドの針が立てられており、そのうちの1本には、天地創造の際に神が置いたとされる64枚の黄金の円盤が刺さっていました。寺院の僧侶たちは、昼も夜も休まずに、ルールに従って円盤を別の針に移し替える作業を続けています。そして、すべての円盤が移し替えられたとき、世界は崩壊し終焉を迎える、と言い伝えられています。

実際に64枚の円盤を移動させる手数を計算すると、2⁶⁴ – 1 = 18,446,744,073,709,551,615回となり、これは1秒に1回動かしたとしても約5845億年かかる計算になります。 この伝説は、考案者であるリュカによる創作と言われていますが、ハノイの塔の持つ数学的な奥深さを示す面白い逸話です。

ハノイの塔は、一見すると子供向けのパズルですが、その本質はコンピュータサイエンスの重要な概念である「再帰」を理解するための優れた教材です。シンプルなルールの中に隠された数学的な美しさと、問題解決のための論理的な思考プロセスは、プログラミング初学者から専門家まで、多くの人々を魅了し続けています。