計算量

「ハノイの塔」という名は、パズル発祥の地を示すものではなく、フランスの数学者エドゥアール・リュカが１８８３年に考案した際に用いた名前です。このパズルは、３本の垂直に立てられた棒と、中心に穴の開いた大きさの異なる複数の円盤で構成されています。円盤の枚数は任意ですが、一般的には３枚以上が用いられます。 ゲーム開始時は、全ての円盤が左端の棒に積み重ねられています。この際、円盤は必ず大きいものから順に、つまり一番大きな円盤が一番下に、一番小さな円盤が一番上にくるように配置されます。プレイヤーの目的は、これらの円盤を全て右端の棒に移動させることです。移動にあたっては、以下の二つのルールを守らなければなりません。一つ目は、一度に移動できる円盤は一枚だけであること。二つ目は、小さい円盤の上に大きい円盤を置いてはいけないということです。つまり、どの棒においても、常に円盤は大きいものから順に積み重ねられていなければなりません。 一見単純なルールですが、円盤の枚数が増えるごとに、パズルを解くための手順は劇的に複雑になります。最小の移動回数を求めるには、２の円盤の枚数乗から１を引いた数で計算できます。例えば円盤が３枚の場合、２の３乗は８、そこから１を引くと７となり、最短で７回の移動で解くことができます。円盤が４枚の場合は１５回、５枚の場合は３１回と、枚数が増えるごとに、最小移動回数は指数関数的に増加します。このため、ハノイの塔は、アルゴリズムや再帰的思考を学ぶための教育教材としても活用されています。単純なルールの中に潜む奥深い論理は、多くの人々を魅了し続けています。