Tower of Hanoi

ハノイの塔の遊び方

ハノイの塔は定番の再帰パズルです。すべての円盤は最初、大きいものが下になるように左の杭に積まれています。ルールは2つ——動かせるのは杭の一番上の円盤だけ、そして大きい円盤を小さい円盤の上に置いてはいけません。この2つを守りながら、円盤を1枚ずつ右の杭へ移し、塔全体を移動させます。杭をクリックして一番上の円盤を持ち上げ、別の杭をクリックして置きます。できるだけ少ない手数で、右の杭に塔を積み直すのが目標です。

最小手数と 2^n−1 の公式

n 枚の円盤のハノイの塔を解くのに必要な最小手数は、ちょうど 2ⁿ − 1 です。3枚なら7手、4枚なら15手、5枚なら31手かかります。この下限を破る手順は存在しないので、ランキングで 2ⁿ − 1 と等しいスコアは完璧な最適解です。

再帰による解法の戦略

• n 枚の円盤を元の杭から目的の杭へ移すには、まず上の n − 1 枚を予備（補助）の杭へ移します。
• 一番大きい円盤を、元の杭から目的の杭へ直接移します。
• 最後に、予備の杭にある n − 1 枚を、一番大きい円盤の上へ移します。それぞれの部分的な積み重ねも同じ方法で、円盤が1枚になるまで解いていきます。

ハノイの塔を最小手数で解くには？上の再帰を当てはめます。問題を「n−1 枚をどける、一番大きいものを移す、n−1 枚を戻す」に分割します。もう一つ簡単な反復のコツもあります——1手おきに最小の円盤を同じ循環方向へ動かし、その間に唯一の合法手を指す——これで同じ最適な 2ⁿ − 1 手の手順が再現できます。