ハノイの塔の攻略｜3枚の手順と4枚・5枚の最短手数

ハノイの塔は、大きい円盤を動かす準備から考えます。3枚を7手で移す盤面を1手ずつ確かめ、4枚が15手、5枚が31手になる理由と、公式を使える条件を説明します。

ハノイの塔を攻略するコツは、いちばん大きい円盤を動かせる形を先に作ることです。その上の円盤を残りの柱へよけ、大きい円盤を運び、よけた円盤をその上に戻します。このページでは、3本の柱を使い、全円盤が1本に積まれた標準形を扱います。

大きい円盤を動かす準備をする

円盤は一番上の1枚だけ動かせます。小さい円盤の上に大きい円盤は置けません。目標はAの3枚をCへ移すこと。円盤3をAからCに動かすには、上にある1と2をBにまとめ、Cを空けます。

図1：開始形。数字が大きいほど大きい円盤です。

途中でBに円盤を積むのは遠回りに見えますが、円盤3を動かすための準備です。小さい円盤をすぐCへ集めようとすると、大きい円盤の置き場所をふさいでしまいます。

最初の3手で円盤1と2をBへ、4手目で円盤3をCへ、最後の3手で残りをCへ移します。図は各操作が終わった状態です。

図2（1手目）：柱Aの一番上を柱Cへ。

図3（2手目）：柱Aの一番上を柱Bへ。

図4（3手目）：柱Cの一番上を柱Bへ。小さい2枚をよけられました。

図5（4手目）：柱Aの一番上を柱Cへ。いちばん大きい円盤がゴールへ移りました。

図6（5手目）：柱Bの一番上を柱Aへ。

図7（6手目）：柱Bの一番上を柱Cへ。

図8（7手目）：柱Aの一番上を柱Cへ。3枚がそろって完成です。

3本の柱で、全円盤を1本から別の1本へ移す標準形の最短手数は2のn乗−1です。nは円盤の枚数を表します。

4枚なら、上の3枚をよけるのに7手、円盤4を動かすのに1手、上の3枚を戻すのに7手で、合計15手です。最大の円盤を動かす前後に、残りの円盤を移す必要があるため、「1枚少ないときの手数×2＋1」となります。同じ手順を繰り返せば実際にその手数で完成できます。

枚数が増えても全手順を丸暗記する必要はありません。「上の円盤をどこへよければ、最大の円盤を目標へ運べるか」を考え、その小さい山に同じ考え方を使います。

練習1Aに円盤3、Bに下から2・1、Cは空です。次は何を動かしますか？

答えと考え方を見る

円盤3をAからCへ動かします。小さい2枚をBへよけ終えたので、最大の円盤を運べます。その後は、円盤1をB→A、円盤2をB→C、円盤1をA→Cの順です。

サイトの円盤移しでは、最初から円盤が複数の柱に分かれた問題もあります。その場合に2のn乗−1をそのまま最短手数として使うことはできません。目標の柱も問題ごとに確かめてください。

散らばった配置の見方や操作は円盤移しの入門で説明しています。まず目標へ移す必要がある最大の円盤を見つけ、その上と行き先を空けるところから試してみましょう。

参考：同志社中学校「『ハノイの塔』で数学しました！」（2015年春。標準形の3枚・7手を扱う資料）。図と手順はこの記事用に作成しています。