読み方：ハノイのとう

概要

ハノイの塔（Tower of Hanoi）とは、直径の異なる複数の円盤を、3本の杭の1本から別の1本にすべて移動させるクイズ。小さな円盤の上に大きな円盤を乗せることはできないという制約のもとで移動させる。

3本の杭が並んでおり、中心に穴の空いた大きさの異なる円盤が複数ある。最初はすべての円盤が1本の杭に刺さっており、一度に一枚ずつ、いずれかの杭の最も上に乗っている円盤を他の杭に移動させるという操作を繰り返す。

すべての円盤を別の1本の杭に移動させたら終了となる。移動は何度繰り返しても良いが、山の途中の円盤を抜き取ることはできず、持ち上げた円盤は、それより小さな円盤の上に乗せてはいけない。n枚の円盤からなるハノイの塔は、最低でも2ⁿ-1回の移動が必要であることがわかっている。

手順

初期状態で最も下にある最も大きな円盤を、目的の杭の一番下に移動させなければならないため、上から2番目に大きい円盤までを一旦3本目の杭に移し、最も大きい円盤を目的の杭に移動させる。

次に、一時的に移動した円盤の山から、やはりその最も下にある2番目に大きい円盤を目的の杭に移さなければならない。そのために、上から3番目に大きい円盤までを最初の杭に移し、2番目に大きい円盤を最も大きい円盤の上に移す。

このように、「その時点で山の最も下にある円盤」を目的の杭に移すため、「山の下から2番目までを一旦別の杭に移す」という操作を繰り返していくことになる。これをコンピュータプログラムで実行するには再帰処理が適しているため、古くからアルゴリズム研究・教育の題材として用いられてきた。