積み木のようなパズルとして有名な「ハノイの塔」の解き方のコツ・必勝法を解説していきます。段数が増えてきても、基本的な解き方を抑えていれば、必ず別の場所に塔を建てることができます。ルールに関しても解説しています。
数学的な考察や歴史についてはこちら↓
ハノイの塔のルール
ハノイの塔は、簡単なルールに従って、円盤が積み上げられてできている塔を別の場所に移し替えるゲームです。
ルールは以下の通りです。
- 棒に刺す形で重ねられた円盤を別の棒に移動する
- 円盤は上からしか取れない
- 動かす円盤は自分より大きな円盤の上にはおけるが、自分より小さな円盤の上にはおけない
- 別の棒に元どおり下から大きい順に重ねた状態にできたらクリア
塔を移し替える場所は、別のところに立てればオーケーという場合と、一番反対側の棒にうつしかえること、となっている場合があります。
いずれにせよ、解き方は同じです。（一本ずつずらしていけば最終的に反対側にたどり着くため。）
ウェブ上でもでき、以下のようなページで遊べます↓
ハノイの塔の解き方・必勝法
ポイントは、以下の通りです。
・一番下の円盤を移すのが最優先
・下から順に移し替えていく
・上の円盤はその間、空いている棒にまとめておく
以下、各段数の場合について図解していきます。
1段・２段の場合
1段、2段はとても簡単ですね。
1段の時は移せば終わりです。
2段の時は1段目を隣に移し、2段目を移してからその上に1段目を置くだけです。
３段の場合
ハノイの塔が実際にパズルとして出題されるのは、３段の場合からがほとんどでしょう。以下、上から円盤を数字で表現します。
１．まずは1と2をずらし、2のところにまとめます。（2段の時と同じ）
2．3を移動します。そして1と2をばらします。
３．2を3の上に置き、最後に1を置いて完成です。
４段の場合
さて、ここにきて棒の本数より円盤の数のほうが増えました。ここでも、流れは同じです。
１．１と２を別のところに重ねます（2段の時と同じ）。3を移動します。
２．１を４の上、２を３の上に重ねます。
３．１を２の上に移すと４が動かせるようになるので、移動します。
４．1を４のうえに、2を空いている棒にばらします。
５．１を2の上に置き、3を4の上に置きます。
６．1をいったん空きに移動させ、2を重ねた後で1を置けば完成です。
５段以上も、前の段数の解き方を応用するのがコツ
ここまで書かれるとわかると思いますが、ハノイの塔の解き方は、前の段数の解き方を再利用して解いていくのが基本的なコツとなります。
上のポイントで書きましたが、一番下の円盤を動かせるように上の円盤をまとめる、というところからはじめて、あとは下から順に移していくと、最終的にどんな段数でも完成できます。
ただし、段数が多すぎると現実的な時間では完成させることができなくなっていく、ということが知られています。
まとめ
- ハノイの塔は、大きい順に重ねられた円盤を、ルールに従って移動させるパズル。
- 必勝法があり、大きい順に移動していくのが解き方のコツ。
- 前の段数の解き方をうまく利用するのもコツ。
ハノイの塔はプログラミングの題材としても有名ですが、パズルが作られた当時は題材になるとは予想されていなかったのではないでしょうか。
