ハノイの塔（４）
こういう説明の難しいところは、説明する側が自分の分かりやすい方法で説明しがちなことです。説明される側は、必ずしも同じイメージが持てません。何度説明しても、やってみるとうまく行かないことが、しばしばあります。難しいものです。今までの説明で、ピンとこない方は、まず、やってみてください。「ハノイの塔」は教育玩具として市販されています。わざわざ買うほどでもない、と思う方は、大きさの違う厚紙を切り抜いても構いません。その場合は、色分けをしておくと、間違わずに済むでしょう。
さて、「ハノイの塔」の最小手数のアルゴリズムを理解すると、7段を何分くらいでクリアできるでしょうか。今度は、総手数が問題です。答えは、255手（=2の7乗-1）です。1手を1秒で、なおかつ、間違わずに進められれば、255秒、つまり4分15秒で終わるはずです。この領域になると、数学パズルというよりは、単なる手の運動になってしまい、当然、若い人の方が有利です。さすがに、「数える」方法を編み出したアテンダントのレコードは4分20秒程度でしたが、私などでは4分50秒ほどかかってしまいます。しかも終わった後は、肩こりと腱鞘炎まがいの腕の痛みが残ります。
この7段で255手、の考え方はいろいろあるようですが、今までの説明をベースにすれば、次のような考え方になります。一段の山、つまり1段目を右の柱に移すのに1手、2段の山を中央に作るのに2手、3段の山を右に作るのに4手かかります。この辺からは、やってみないと理解しにくくなりますが、4段の山を中央に作るのに8手、5段の山を右に作るのに16手、6段の山を中央に作るのに32手、7段の山を右に作るのに64手かかることが分かります。これだけの手数が必要なので、合計すると、1+2+4+8+16+32+64=255となります。2の7乗は256なので、2の段数乗から1を引くと、総手数になります。なぜ1を引くのかといえば、最初の状態を数えないからです。最初の状態を入れた全パターンが、2のn乗（nは段数）ということになります。試行錯誤でやると20分から30分かかるのが、最小手数のアルゴリズムを理解すれば4分ちょっとでできるわけです。
さて、意地悪をして「ハノイの塔」を8段にしてみました。7段で30分かかる人は、8段では1時間以上かかることになります。なぜかというと、7段をまず作ってから、その7段の山を隣に移すことになるためです。7段の手数の2倍と、8段目を移す1手が必要になるわけです。したがって、2×255+1=511となって、確かに2の8乗-1になりました。また、1手1秒で計算すると、最小手数では、8分41秒となります。しかし、実際にトライしてみると、疲れが出てくるのか、とても計算通りの時間では終わりません。10分近くかかってしまいました。それでも、試行錯誤の60分に比べれば、50分も少なくて済みます。でも、これでは単なる手の運動に過ぎません。何分何秒でクリアするかという、新記録だけが目的になってしまいます。科学の行き着く先としては、どうなのかな、という結果になってしまいました。お疲れさまでした。
「ハノイの塔」の最小手数のアルゴリズムを理解するためのヒントは、別のホームページ(http://www.icnet.ne.jp/~nandemo_lab/index.html) に掲載しましたので、興味のある方はご覧ください。
