ハノイの塔(n=4)

AAAA

• 台の上に3本の棒が十分に離れて垂直に立っている．
• 全て異なる大きさの，穴のあいた4枚の円盤が，その棒に貫かれる形で置かれている．
• 最初の状態では，4枚の円盤は同じ1本の棒に， 大きい円盤は下方に，小さい円盤は上方になるようにして，大きさの順に置かれている．
• これらの円盤を，以下の条件を満たすように，棒から棒へ動かして，全ての円盤を別の棒に移したい．
  条件は以下の通り：
  • 円盤は，1枚ずつ棒から棒へ移動させる．
  • 円盤は，自分自身より小さい円盤の上に置いてはいけない．
• どのように円盤を動かせばよいか?