ハノイの塔

ゲーム

ハノイの塔

はのいのとう

[英] Tower of Hanoi

ハノイの塔は、はパズルの一つ。

1883年フランス数学者エドワール・リュカが考案したパズル。

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

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

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

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

n枚の円盤すべてを移動させるには最低 2^n - 回の手数がかかることがわかっている。

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

D