ハノイの塔 - ITエンジニアノイのブログ

ハノイの塔は、数学的なパズルゲームの一つで、フランスの数学者エドゥアール・リュカが1883年に考案しました。このゲームの目的は、一連のルールに従いながら、ディスクを一つの柱から別の柱へ移動させることです。小さなディスクから始まって大きなディスクまで順に積み重ねられたディスクを、始点の柱から他の柱へと移動させるパズルゲームです。

ルール

ディスクの移動: ゲームは、サイズが異なる複数のディスクと、それらを挿入できる3つの柱で構成されています。これらのディスクは最初に一つの柱に小さいものが上になるように順番に積み重ねられています。
一回に一つのディスク: 一度に一つのディスクだけを別の柱へ移動させることができます。ディスクは柱の上から取り除かれ、別の柱の上に置かれます。
大きなディスクの上に小さなディスクを置けない: 小さなディスクの上にのみ大きなディスクを置くことができます。つまり、どの柱にも、より大きなディスクがより小さなディスクの上に来ることはありません。

目標: すべてのディスクを、最初の柱から他の柱の一つに、上記のルールに従って移動させることです。ただし、最終的にはディスクの順番が初期状態と同じになるように積み重ねられていなければなりません。

このパズルは、最小の移動回数で解くことが目標です。ディスクの数が増えると、必要な手順の数は指数関数的に増加します。例えば、ディスクが3枚ある場合の最小移動回数は7回、4枚の場合は15回です。ディスクの数がn枚の場合、解くのに必要な最小移動回数は (2ⁿ - 1) 回です。