ハノイの塔

ハノイの塔（ハノイのとう、Tower of Hanoi）はパズルの一種。 バラモンの塔または ルーカスタワー とも呼ばれる。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。

最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。

円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには最低 2n - 1 回の手数がかかる[1]。

解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。