ハノイの塔

ハノイの塔の遊び方（ルール）

• 左の棒に重なった円盤を、全部右の棒へ移すパズルゲームです。
• 円盤は1回に1枚ずつ、いちばん上のものだけを動かせます。小さい円盤の上に、大きい円盤は置けません。
• 動かしたい円盤のある棒を押してから、移したい棒を押します。円盤をドラッグして動かすこともできます。パソコンでは 1・2・3 のキー（左・真ん中・右の棒）でも動かせます。
• 円盤の数は3段〜10段から選べます。初めての方は3段か4段から始めて、最短手数でそろえられたら1段ずつ増やしてみましょう。
• 「今日の問題」は1日1問で、日本時間の0時に変わります。5枚の円盤が3本の棒にばらばらに重なった所から、全部を右の棒へ移します。だれが遊んでも同じ問題で、最短手数は問題ごとに違います。ヒントを使ってもクリアに数えますが、「解き方」を見た回は数えません。
• 困ったら「ヒント」で、いまの並びからの最短の次の一手が光ります。「解き方」を押すと、そこから最短の解き方で円盤が自動で動きます（もう一度押すと止まります）。ヒントや解き方を使った回は、自己ベストに数えません。途中でページを閉じても、次に開いたときに続きから遊べます。

ハノイの塔の最短手数と公式

円盤が n 枚（n 段）のときの最短手数は、公式 2ⁿ−1 手（2を n 回かけて1を引いた数）で求められます。1段増えるごとに、約2倍になります。

なぜこの手数になるかは、いちばん大きい円盤で考えると分かります。いちばん大きい円盤を右の棒へ動かすには、その上の n−1 段を全部真ん中の棒へよけておく必要があります。そのあといちばん大きい円盤を右へ1手で動かし、よけた n−1 段をその上へ移します。n 段の手数は「n−1 段の手数 × 2 ＋ 1」になるので、3段なら 2段の3手×2＋1＝7手、4段なら 3段の7手×2＋1＝15手と増えていきます。

ハノイの塔の解き方と攻略のコツ

• いちばん小さい円盤は1回おきに、決まった向きへ回す：段数が奇数（3・5・7・9段）なら 左→右→真ん中→左…、偶数（4・6・8・10段）なら 左→真ん中→右→左… の順に動かします。
• 小さい円盤を動かさない番は、動かせる手が1つだけ：いちばん小さい円盤が乗っていない2本の棒の間で、上の円盤の小さいほうを大きいほうの上へ（片方が空なら空のほうへ）動かします。
• この2つを交互にくり返すだけで、何段でも最短手数でそろいます。迷ったら、上の n−1 段を「ひとかたまり」と見て、まず真ん中へ、次にいちばん大きい円盤を右へ、最後にかたまりを右へ、と考えましょう。

ハノイの塔とは

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発表したパズルです。「インドの寺院で僧たちが64枚の金の円盤を移し終えたとき、世界は終わる」という言い伝えとともに紹介されました。64枚の最短手数は 18,446,744,073,709,551,615手（約1844京手）で、1秒に1手ずつ動かしても約5845億年かかります。同じ形の小さな問題に分けて解く「再帰」の例として、数学やプログラミングの授業でもよく使われます。