ハノイの塔

ハノイの塔の遊び方

ハノイの塔は、3本の棒と、大きさのちがう円盤を使うひとり遊びのパズルです。左の棒に大きい順に積んだ円盤を、決まりを守りながら1枚ずつ動かして、右の棒へ全部移せば完成です。決まりはたった2つなのに、枚数が増えると手数がどんどん増えていくので、子どもの考える練習にも、大人の頭の体操にも向いています。

はじめとゴール

はじめは、いちばん左の棒に全部の円盤が積んであります。下がいちばん大きく、上へいくほど小さくなっています。これを、いちばん右の「ゴール」の棒に、同じ順番のまま積み直せば完成です。真ん中の棒は、途中で円盤を置いておく場所として自由に使えます。

2つの決まり

決まりは次の2つだけです。

• 1回に動かせるのは1枚だけ。動かせるのは、どれかの棒のいちばん上にある円盤です。下の円盤を先に抜き出すことはできません。
• 小さい円盤の上に、大きい円盤は置けません。置けるのは、空いている棒か、自分より大きい円盤の上です。

このゲームでは、置けない所へ動かそうとすると、円盤が小さくゆれて「大きい円盤は、小さい円盤の上に置けません」と理由が出ます。まちがえても手数には数えないので、安心して試してみてください。

このゲームの画面の使い方

動かしたい円盤のある棒を押すと、いちばん上の円盤がふわっと持ち上がります。続けて置きたい棒を押すと、円盤が横に動いてその棒へ下ります。持ち上げたのをやめたいときは、同じ棒をもう一度押せば元に戻ります。円盤を指やマウスでつかんで、置きたい棒までドラッグしても動かせます。キーボードなら、1・2・3のキーで棒を選べます（4本のときは4も使います）。

画面の上には、今の手数と、その枚数の最短手数、タイムが出ます。タイムは最初の1手を動かしたときから計り始めます。困ったときは「1手もどす」で直前の手を取り消せます。

円盤の数と最短手数

円盤は3枚から8枚まで選べます。どの枚数にも「これより少なくはできない」という最短の手数があり、1枚増えるごとに、だいたい2倍に増えていきます。

最短手数は「2を枚数の回数だけかけて、1を引いた数」になります。3枚なら 2×2×2−1＝7、4枚なら 2×2×2×2−1＝15 です。最短手数ぴったりで完成すると「最短で完成！」と出て、記録にも残ります。

ルールを変えて遊ぶ

設定で「自分で決める」を選ぶと、ハノイの塔の変わりルールで遊べます。

4本の棒では、置き場所が増えるぶん手数がぐっと減ります（3枚5手、5枚13手、8枚でも33手）。反対に「隣の棒だけ」では、3枚でも26手、6枚では728手もかかります。このため「隣の棒だけ」は6枚までにしています。

解き方のコツ

1. まず3枚を7手で解けるようにする

3枚の最短は「1→3、1→2、3→2、1→3、2→1、2→3、1→3」の7手です。何度か解いて、手が自然に動くくらいになると、4枚以上がぐっと楽になります。

2. いちばん大きい円盤から考える

いちばん大きい円盤を右の棒へ動かせるのは、ほかの円盤が全部真ん中の棒に集まっているときだけです。つまり4枚なら、「上の3枚を真ん中へ移す」「いちばん大きい円盤を右へ」「真ん中の3枚を右へ移す」の3段階に分けられます。3枚を移すのは7手なので、7＋1＋7＝15手。5枚なら 15＋1＋15＝31手です。大きな問題を、1枚少ない同じ問題に分けて考えるのがハノイの塔のいちばん大事な考え方です。

3. 1手目は枚数で決まる

最短で解くには、1手目にいちばん小さい円盤をどこへ置くかが大事です。枚数が奇数（3・5・7枚）ならゴールの右の棒へ、偶数（4・6・8枚）なら真ん中の棒へ置きます。逆に置くと、どこかで遠回りすることになります。

4. いちばん小さい円盤は、いつも同じ向きに回る

最短の解き方では、いちばん小さい円盤が1手おきに動き、しかもいつも同じ向きに回ります。奇数枚なら「1→3→2→1…」、偶数枚なら「1→2→3→1…」の順です。

5. 小さい円盤を動かさない手は、1通りしかない

いちばん小さい円盤を動かした次の手は、ほかの円盤を動かす番です。このとき、動かせる手は必ず1通りしかありません（いちばん小さい円盤がいない2本の棒のうち、上の円盤が小さいほうを、もう一方へ動かす）。「小さい円盤を決まった向きへ」「それ以外で動かせる1手」を交互にくり返すだけで、何枚でも最短で解けます。

6. 迷ったらヒントとお手本

「ヒント」を押すと、今の並びから最短で完成するための次の1手が矢印で出ます。途中で遠回りしていても、今の並びからの最短を教えてくれます。「お手本」は、今の並びから完成までを自動で動かして見せます。速さは3段階から選べて、「止めて自分で続ける」でいつでも自分の番に戻れます。ヒント・お手本・1手もどすを使った回は、自己ベストの記録には入りません。

よくある質問

いちばん少ない手数は何手？

3本の棒なら、円盤が n 枚のときの最短手数は「2のn乗−1」手です。3枚7手、4枚15手、5枚31手、6枚63手、7枚127手、8枚255手になります。

64枚だと、どのくらいかかる？

2の64乗−1＝18,446,744,073,709,551,615手、およそ1845京手です。1秒に1手ずつ休まず動かしても、約5850億年かかる計算になります。

棒が4本だと、最短は何手？

4枚9手、5枚13手、6枚17手、7枚25手、8枚33手です。4本のときの最短の手数は長いあいだ予想のままでしたが、2014年に証明されたと発表されています。棒が5本以上のときは、今もはっきり分かっていません。

タイムはいつから計るの？

最初の1手を動かした時から、完成するまでです。始める前にじっくり考えても、タイムには入りません。自己ベストは、円盤の数とルールごとに、この端末に記録されます。

途中でやめても続きから遊べる？

同じ端末・同じブラウザで開けば、設定画面の「続きから」で、円盤の並びと手数ごと再開できます。はじめは音が出ない設定です。「音：オフ」を押すと、円盤を置いたときや完成したときに効果音が鳴ります。

ハノイの塔ってどんな遊び？

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に売り出したパズルです。はじめは自分の名前の文字を並べかえた別の名前で発表しました。このパズルには、「インドの寺院で僧侶たちが64枚の金の円盤をこの決まりで動かし続けていて、全部を移し終えたとき世界が終わる」という言い伝えが添えられていましたが、この話はリュカ自身が考えた作り話だとされています。とはいえ、64枚を移すのにかかる時間を計算すると、世界が終わるのが先か、円盤が移し終わるのが先か、どちらにしても気の遠くなる話です。今では、同じ考え方をくり返して大きな問題を解く「再帰」の例として、算数やプログラミングの学習にもよく使われています。