ハノイの塔


ハノイの塔(1)

 

 科学館の展示物の中には、科学パズルも何点かありました。その一つが、「空中コマ」の隣にあった「ハノイの塔」です。他の展示物との違いは、何と言っても時間がかかることです。普通、展示物は大勢に使ってもらいたいので、長時間独占されるのは困ります。多くの展示物は、せいぜい数分で、長くても10分も占有されることはありません。例外が、「アルゴブロック」と、「空中コマ」と、この「ハノイの塔」でした。一応、「アルゴブロック」は、10分以内という制限を表示してありましたが、「空中コマ」と「ハノイの塔」は無制限でした。無制限でも、できない人は5分も続けると、あきらめてしまいます。平均的には、無制限でも構いませんでした。しかし、できるまで粘る人が現れると、「空中コマ」では1時間以上も、「ハノイの塔」では2時間も占有されることがありました。まあ、極めて稀なケースでしたが。

 面白いもので、混んでいるときでも、「ハノイの塔」には待ち行列ができません。誰かさんが悩んでいるのを見ると、難しいと思って敬遠するようです。それとは逆に、「空中コマ」では、誰かさんができないでいると、周りで見ている人に、がぜん挑戦欲がでてくるのか、「代わって」と言い出す人が大勢いました。別の言い方をすれば、どちらも混んでいないときには、格好の暇つぶしになっていたわけです。もっとも、個人的には「ハノイの塔」は単なるパズルと思っていたので、一回チャレンジして難渋し、20分以上もかかってしまったので、その後は敬遠していました。パズルと考えると、課題がクリアできさえすれば、手順や手数はどうでもいいので、子どもたちは悩むことなく、馬力でクリアしてしまいます。そのやり方でも、コツをつかめば30分程度でクリアできます。でも、もう一度やれ、と言われても、同じにはできません。

 実は、「ハノイの塔」は数学パズルなので、最小手数が決まっています。その最小手数のアルゴリズムを理解すれば、何度でも同じやり方でクリアできることになります。「ハノイの塔」に挑戦して、途中で行き詰っている人の大部分は、この最小手数のプロセスから外れている人たちです。単純に次の手が分からなくなっているのではなく、堂々巡りを始めてしまった人たちです。そういう状況では、分かっていても簡単には指導できません。そういう意味もあって、長らく「ハノイの塔」は、避けていました。

 

 しかし、あるとき、いたずら心が芽生えました。科学館の「ハノイの塔」は7段だったので、最小手数は255手です。7段であれば、子どもが試行錯誤しても30分もあればクリアします。でも、それは、単なるパズルを楽しんだのであって、科学にはなっていないのではないか、と考えたのです。8段にすると最小手数は7段の2倍の511手になります。7段の試行錯誤で30分ならば、8段では1時間かかるはずです。こうなると、試行錯誤でクリアするのは難しくなり、最小手数のアルゴリズムを自分で見つける必要が生じます。8段にしてやろう、といことで、1段追加しました。そうなると、最小手数のアルゴリズムに気がつくようなヒントが必要になります。自分なりに考えて、そのヒントを説明文に加えました。でも、子どもたちはそれには頓着しません。役に立ったのは、お父さんやお母さんだったようです。子どもができるのに、親ができないと面目丸つぶれなので。


ハノイの塔(2)

 

 最小手数のアルゴリズムに興味を持ったきっかけは、あるアテンダントの見事な手さばきでした。7段の「ハノイの塔」を苦もなく7分以内で仕上げます。「どうやるの?」と聞くと、「大体覚えています。迷ったら数えます。」という答えだったので、「どうして数えるとできるの?」と聞いた答えは、「分からないけど、できます。」でした。試してみると、その通りです。「数えるとできる」ことは分かりましたが、なぜ、が説明できないと科学とはいえません。「ハノイの塔」は数学パズルとしてはメジャーなので、解説もいろいろとあります。しかし、数学的な解説は一般には難し過ぎます。解説を参考にして、以下のような結論になりました。その前に、約束ごとです。

 

ブログで図形を説明するのは難しいので、ここでは、「ハノイの塔」の3本の柱を、左、中央、右、と表記します。また、最も小さい板からピラミッド型に続く、一連の山を段と言うことにします。2段の山、3段の山、などです。さらに、一枚一枚の板は、小さい方から何段目と言うことにします。一番小さい板は1段目で、一番大きい板は7段目です。

 

 さて、「左にある7段の山を、右に移せ」というのが課題としましょう。「ハノイの塔」のルールは2つで、「1回に移動できるのは1枚」、「より小さい板の上に、より大きい板は置けない」というのが制約です。小さい子が7段の山を持ち上げて、そのまま移すのはダメ、小さい方から1段ずつ移して、小さい板から順に大きい板を積み上げるのもダメ、ということです。初めての人がやると、1段目を右に移し、2段目を中央に移したところで、進まなくなります。3段目を移したくても、右の柱も中央の柱も3段目より小さな板が既にあります。その上に載せることはできません。ここであきらめる人も少なからずいます。では、どうすればいいか。そう、右の1段目を中央の2段目の上に移せば、右の柱が空きます。そこに3段目を移せばよいのです。これが分かれば、後はその要領で進められます。

 子どもたちの多くも、そこから先は試行錯誤の繰り返しです。なかなか順調には進まず、堂々巡りを繰り返すこともありますが、修正を重ねるうちになんとかクリアしてしまうものです。子どもの方が記憶力がよいのでしょう、正しい方法を感覚的に覚えてしまうので、だんだん調子が良くなるようです。しかし、大人はそうは行かないみたいです。泥沼に入り込んで、無限(無間)地獄の苦しみを味わっています。それでも、少しでも進むことができれば、さらに進もうとするので、ますます泥沼に入り込むのを黙ってみているスタッフたち。どうにもならなくなると、目を上げてスタッフに救いを求めてきます。やっと我々の出番です。最初に教えてしまうのでは、意味がありません。苦しんだ挙句なので、説明がよく分かり、救いにもなる、という、よくあるパターンです。何かに似ていますね。


ハノイの塔(3)

 

 7段の「ハノイの塔」の最小手数の考え方は、次のようなものです。手順とは逆に、まず、最後に、右に7段の山を作るためには、中央に6段の山ができなければならない、と考えます。つまり、7段目を右に移すためには、右の柱を空けておかなければならないからです。左に7段目が残っていて、中央に6段の山ができていれば、次の手で7段目を左から右に移すことができます。逆に言えば、それ以外の方法はありません。その次に考えるのは、中央に6段の山を作るためには、右に5段の山ができないといけない、ということで、その後は、順に、中央に4段の山、右に3段の山、中央に2段の山、右に1段の山となりますが、1段の山とは1段目、つまり一番小さい板ということです。最初の1手は、1段目を左から右に移す、が正解です。何も考えないで、1段目を中央に移してしまうと、7段の山は中央にできてしまいます。それでも山を移したことにはなりますが、課題とは違う結果になってしまいます。

 さて、この説明を聞くと、なぜ、右と中央だけなのか、と思う人もいるでしょう。それは、元々の山が左にあるからです。元々の山の一部が常に左に残っているので、段を作ることができるのは右と中央だけということになります。これで分かったことと思いますが、「数える」という真意は、段数を逆に数えるということなのです。つまり、(1)右7段の山→(2)中央6段の山→(3)右5段の山→(4)中央4段の山→(5)右3段の山→(6)中央2段の山→(7)右1段の山(1段目)、となります。

 

 しかし、これだけでは、説明としては不十分です。中間の目標をたどっただけなので、この途中には、中途半端な山が、左、中央、右の柱に次々とできます。この中途半端な山、つまり、整然と積まれていない、中間の大きさの板が抜けた山が迷いの元なのです。中間の目標を忘れてしまうと、この中途半端な山を見ても、この先どうすれば良いのか、判断に苦しみます。ある中間の目標から次の中間の目標へは、一気にたどりつく必要があります。そのためにこそ、この「数える」方法が役に立つのです。例えば、中央に6段の山ができたとしましょう。次の手で左の7段目を右に移すことになりますが、その後はどうすればよいでしょうか。中央の6段の山を右に移すには、一時、7段目のことは忘れて、(1)右6段の山→(2)左5段の山→(3)右4段の山→(4)左3段の山→(5)右2段の山→(6)左1段の山(1段目)、となるので、1段目を中央から左に移すのが最初の手となります。何段かの山を間違えずに移動するためには、その山のある柱を除いた残りの柱を、移したい柱を起点にして山の段数まで交互に数え、最終点になった柱に一段目の板を移せばよいのです。途中で分からなくなっても、何段の山をどこへ、がはっきりしていれば、この方法が役に立ちます。

 要するに、最終目標は一時忘れて、次の中間目標までを一気に進めること、がポイントです。そのためには、3段や4段の山の移動方法は覚えてしまった方がスムーズに行きます。それができるようになれば、後は「数える」方法が迷ったときのガイドになります。


ハノイの塔(4)

 

 こういう説明の難しいところは、説明する側が自分の分かりやすい方法で説明しがちなことです。説明される側は、必ずしも同じイメージが持てません。何度説明しても、やってみるとうまく行かないことが、しばしばあります。難しいものです。今までの説明で、ピンとこない方は、まず、やってみてください。「ハノイの塔」は教育玩具として市販されています。わざわざ買うほどでもない、と思う方は、大きさの違う厚紙を切り抜いても構いません。その場合は、色分けをしておくと、間違わずに済むでしょう。

 

 さて、「ハノイの塔」の最小手数のアルゴリズムを理解すると、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) に掲載しましたので、興味のある方はご覧ください。


HOME