ハノイの塔は、3本の柱に積まれた大きさのちがう円盤を、1枚ずつ動かして右の柱に積みかえるパズルです。円盤が3枚ならすぐ解けますが、7枚になると、何から動かせばよいのかわからなくなります。ところが、いちばん大きい円盤から順に「どの柱へ動かすか」を決めると、円盤がいくつあっても同じ考え方で、画面に出る最短手数どおりに解けます。この記事では、その考え方を図で追います。
ハノイの塔のルール
柱は左・中・右の3本で、行き先は旗のついた右の柱です。円盤はすべて大きさがちがい、動かせるのは柱のいちばん上の円盤を1枚だけです。小さい円盤の上に大きい円盤は置けません。すべての円盤を右の柱へ、大きい順に積むと完成です。
動かすには、柱をタップします。いちばん上の円盤が持ち上がるので、移したい柱をタップすると、そこへ移ります。円盤をなぞって動かすこともできます。ゲームの円盤には数字が出ないので、この記事では円盤を大きさで呼びます。いちばん小さい円盤を1番、次を2番と数えます。
置けない場所へ動かそうとしても、円盤は動きません。手数にも数えないので、うっかり間違えても損はしません。
画面の上には、ここまでの手数(「12手」など)と、そのレベルの「最短 N手」が出ます。円盤を1枚動かすごとに1手です。「戻す」で1手を取り消しても、数えた手数は減りません。レベルは全30で、円盤は3枚から7枚まで増えます。
基本の考え方は、いちばん大きい円盤から
いちばん大きい円盤を右の柱へ動かせるのは、ほかの円盤がすべて、残りの1本(左に積んだ形なら中の柱)に集まっているときだけです。大きい円盤の上に円盤が残っていると持ち上げられず、行き先の柱に円盤があると、小さい円盤の上に置くことになってしまうからです。だから、最初に考えるのは「大きい円盤をいつ動かすか」です。
- いちばん大きい円盤以外のすべてを、中の柱へ集める
- いちばん大きい円盤を、右の柱へ動かす
- 中の柱に集めた円盤を、右の柱の大きい円盤の上へ運ぶ
レベル3(円盤3枚)なら、1番と2番を中の柱へ集めるのが3手です。そこで3番を右へ動かし、残りの1番と2番をその上へ運びます。
「ほかの円盤を集める」ところも、考え方は同じです。2枚を中の柱へ集めるなら、「1番を右の柱へどけて、2番を中の柱へ動かし、1番を2番の上へ」。つまり、n枚を動かすには、まず上のn-1枚を別の柱へ動かす、という同じ形が何度も出てきます。円盤が増えても、一番大きい円盤から順に考えれば迷いません。
最短手数は、円盤が1枚増えるたびに「2倍して1足す」ふえ方です。3枚で7手、4枚で15手、5枚で31手、6枚で63手、7枚で127手。左の柱に全部積んだ形から始まるレベルは、レベル3(3枚)・レベル8(4枚)・レベル16(5枚)・レベル25(6枚)・レベル30(7枚)で、最短はこの手数です。
左に全部積んだ形は、1番の円盤のリズムで解ける
左の柱に全部積んだ形から始まるときは、頭で再帰を追わなくても、決まったリズムで手が決まります。レベル3の7手を全部書くと、次のとおりです。
- 小を左の柱から右の柱へ
- 中を左の柱から中の柱へ
- 小を右の柱から中の柱へ
- 大を左の柱から右の柱へ
- 小を中の柱から左の柱へ
- 中を中の柱から右の柱へ
- 小を左の柱から右の柱へ
奇数手目(1・3・5・7手目)は、すべて小(1番)です。1番を1手おきに動かし、その間の1手は、1番がいない2本の柱の間で動かせる円盤を動かすだけです。動かせる円盤は、2本の柱のいちばん上を見比べて、小さいほうを相手の柱へ動かす(空の柱があれば、そこへ動かす)ので、1つに決まります。
1番の動かす向きだけ覚えておきます。1番は同じ向きに回り続けます。円盤が3枚・5枚・7枚(奇数)のときは、左→右→中→左の順、4枚・6枚(偶数)のときは、左→中→右→左の順です。レベル3は3枚なので、1手目は右の柱へ、次は中の柱へ、その次は左の柱へ動かします。右の柱が行き先なのに、いったん中や左へ動かすのは遠回りに見えますが、1番がそこへ回っていくことで、ほかの円盤が動けるようになります。
このリズムは、左に全部積んだ形から始めるレベルで使えます。途中でどう動かせばよいかわからなくなったら、次の節の決まりで並びを見直してください。その決まりは、どんな並びからでも使えます。
散らばった形から始まるレベルは、大きい円盤から見ていく
レベル1のように、円盤が柱に散らばった形から始まるレベルは、左に積んだ形より最短手数が少なくなります。たとえば3枚のレベル1は5手で、積んだ形の7手より短いです。ここでは、大きい円盤から順に、動かす必要があるかを見ていく決まりを使います。
- いちばん大きい円盤から順に、1枚ずつ見る。最初の行き先は、旗の右の柱
- 見ている円盤がもう行き先の柱にいれば、動かさない。次に大きい円盤へ進み、行き先はそのまま
- いなければ、その円盤を行き先の柱へ1回だけ動かす。そのために、それより小さい円盤をすべて「残りの1本」(その円盤のいる柱でも行き先でもない柱)に集める。小さい円盤の行き先は、この残りの1本になる
- その円盤を動かしたら、集めた円盤をその上へ運ぶ
レベル1で追ってみます。3番は中の柱にいて、行き先の右の柱にはいません。そこで、1番と2番を残りの1本(左の柱)に集めます。2番はもう左の柱にいるので動かさず、右の柱にいた1番だけを左の柱へ動かします。
これで3番を右の柱へ動かせます。動かしたあとは、1番を中の柱へ、2番を右の柱へ、1番を右の柱へ、の3手です。合計5手で、画面の「最短 5手」と同じです。
図の3番のように、いちばん大きい円盤がもう右の柱にいる並びなら、それは動かしません。動かすと、ほかの円盤をまた集めてやり直すことになり、遠回りになるだけです。大きい円盤を動かさずに済むかを、まず確かめましょう。
手数の見積もり方
この決まりに従うと、最短手数がレベルを始める前に計算できます。k番の円盤を動かす必要があるとき、その円盤の分は、1に2をk-1回かけた手数です(1番は1手、2番は2手、3番は4手、4番は8手、5番は16手、6番は32手、7番は64手)。k番の1手と、集めた円盤をその上へ運ぶ分を合わせた数です。動かさずに済む円盤は0手で、全部を足した数が最短手数です。
レベル5(円盤4枚)で計算してみます。4番は中の柱にいて、右の柱にはいないので、8手。行き先は残りの左の柱に変わります。3番は左の柱にいて、そこが行き先なので、0手。2番は右の柱にいて、左の柱にはいないので、2手。行き先は残りの中の柱に変わります。1番は左の柱にいて、中の柱にはいないので、1手。合計は8+2+1=11手で、画面の「最短 11手」と同じです。
この決まりは、途中のどんな並びからでも使えます。うっかり順番を間違えても、そのときの並びから、あらためて大きい円盤から見直せば、残りの手数がいちばん少ない道に戻れます。
手数を減らすコツ
- 先に大きい円盤の行き先を決める。いちばん大きい円盤を動かす必要があるかを確かめると、小さい円盤をどの柱へ集めるかが決まり、迷わず動かせます。
- 「戻す」は手数を減らさない。戻しても、すでに数えた手数はそのまま残ります。動かす前に、いちばん大きい円盤の行き先を確かめておくほうが得です。
- 「最初から」も手数を減らさない。手数は0に戻らずそのまま足されていき、画面の時間だけが0に戻ります。
最短手数を超えても失敗にはなりません。同じ手数で完成できれば、いちばん少ない手数です。ゆっくり考えて、最短を目指してみましょう。
脳タイムのハノイの塔で実践する
脳タイムのハノイの塔は、レベル1から30まであります。円盤はレベル1から3が3枚、4から8が4枚、9から16が5枚、17から25が6枚、26から30が7枚です。レベル3・8・16・25・30は左の柱に全部積んだ形から始まり、そのほかのレベルは円盤が散らばった形から始まります。レベル30の最短は127手です。
どのレベルにも、失敗も時間切れもありません。レベル5までは登録なしでそのまま遊べます。レベル6から24はテオワンIDでログインすると開放され、レベル25から30はポイントで開放する最上位帯です。タイルを動かして並べるパズルも遊びたい方は、15パズルの解き方もあわせてご覧ください。
