ハノイの塔

この記事は第359回今週のオススメ記事（2015/5/5）に選ばれました！ よりニコニコできるような記事に編集していきましょう。

ハノイの塔とは、パズルゲームの一種である。

概要

3本の棒と、中心に穴のあいた何枚かの異なる大きさの円盤がある。ゲームスタート時は一番左の棒に下から大きい順に円盤が積み重ねられており、所定のルールに従って全ての円盤を一番右の棒に移動させていく。

単純で理解しやすいゲームであり、小学校や中学校で算数・数学の教材に使われることもある。

ルール

• 一手につき1枚しか円盤を動かすことはできない。
• ある円盤の上に、それより大きい円盤を積むことはできない。
• 棒以外のところに円盤を移動させることはできない。

最短手数

上記のルールに従ってn枚の円盤を一番左の棒から一番右の棒へと動かす場合、最少でも2ⁿ-1の手数が必要となることが知られている。たとえば、3枚の場合なら2³-1=7となり7手必要である。また、最短手数の場合、奇数の手（1手目、3手目、5手目…）は一番小さい円盤を動かす手であり、その次の偶数の手（2手目、4手目、6手目…）は1通りしかない。

3段

［画像クリックで1手進む］

1手目

［←］［→］

2手目

［←］［→］

3手目

［←］［→］

4手目

［←］［→］

5手目

［←］［→］

6手目

［←］［→］

7手目

［←］［最初に戻る］

4段

［画像クリックで1手進む］

1手目

［←］［→］

2手目

［←］［→］

3手目

［←］［→］

4手目

［←］［→］

5手目

［←］［→］

6手目

［←］［→］

7手目

［←］［→］

8手目

［←］［→］

9手目

［←］［→］

10手目

［←］［→］

11手目

［←］［→］

12手目

［←］［→］

13手目

［←］［→］

14手目

［←］［→］

15手目

［←］［最初に戻る］

5段

［画像クリックで1手進む］

1手目

［←］［→］

2手目

［←］［→］

3手目

［←］［→］

4手目

［←］［→］

5手目

［←］［→］

6手目

［←］［→］

7手目

［←］［→］

8手目

［←］［→］

9手目

［←］［→］

10手目

［←］［→］

11手目

［←］［→］

12手目

［←］［→］

13手目

［←］［→］

14手目

［←］［→］

15手目

［←］［→］

16手目

［←］［→］

17手目

［←］［→］

18手目

［←］［→］

19手目

［←］［→］

20手目

［←］［→］

21手目

［←］［→］

22手目

［←］［→］

23手目

［←］［→］

24手目

［←］［→］

25手目

［←］［→］

26手目

［←］［→］

27手目

［←］［→］

28手目

［←］［→］

29手目

［←］［→］

30手目

［←］［→］

31手目

［←］［最初に戻る］

円盤の枚数を変える

• 3枚（7手）
• 4枚（15手）
• 5枚（31手）

最短手数についての解説

このゲームを最短手数で終わらせる際、次のような手順で解いていくことになる。

1. 左の棒に積み重なっている円盤のうち、一番下以外の円盤を何らかの方法で真ん中の棒に移す
2. 左の棒に残っている一番大きい円盤を右の棒に移す
3. 真ん中の棒に残っている円盤をすべて何らかの方法で右の棒に移す

さて、ここで気になるのは「何らかの方法」なのだが、これは全体の円盤の枚数より1枚少ない状態でゲームをするのに等しい。例えば、5枚の円盤でゲームをする場合、「4枚の円盤でのゲーム」を2回行っていることになる。これを1枚の円盤で行うゲームから順に適用していくと、次のようになる。

• 1枚：円盤を右に動かす……1手
• 2枚：1枚の円盤を真ん中に（1手）→一番大きい円盤を右に（1手）→1枚の円盤を右に（1手）……3手
• 3枚：2枚の円盤を真ん中に（3手）→一番大きい円盤を右に（1手）→2枚の円盤を右に（3手）……7手
• 4枚：3枚の円盤を真ん中に（7手）→一番大きい円盤を右に（1手）→3枚の円盤を右に（7手）……15手
• 5枚：4枚の円盤を真ん中に（15手）→一番大きい円盤を右に（1手）→4枚の円盤を右に（15手）……31手
• 6枚：5枚の円盤を真ん中に（31手）→一番大きい円盤を右に（1手）→5枚の円盤を右に（31手）……63手
• 7枚：6枚の円盤を真ん中に（63手）→一番大きい円盤を右に（1手）→6枚の円盤を右に（63手）……127手

以上のように回数は増加していき、円盤の枚数がn枚のとき、最短手数は2ⁿ-1回であることが確認できる。より厳密に証明したい場合は数学的帰納法か漸化式を用いれば証明することができる。

伝説

「一番左の棒に64枚の円盤を積み、それら全てを一番右の棒に移し終わったとき世界は滅亡する」という旨の伝説があるが、これは考案者の創作であると考えられている。

前述したとおり、n枚の円盤を移し終えるには最少でも2ⁿ-1の手数が必要であるため、円盤が64枚の場合に必要な手数は途轍もない数となる。仮に一度も間違えることなく1秒に1回のペースで円盤を動かし続けるとすると2⁶⁴-1秒（1844京6744兆0737億0955万1616秒）、約5845億年の時間が掛かることになる。移し終える前に人類は滅亡してしまうだろう。

ちなみに関連動画ではTASさんの力をもってしても127手に0.43秒かかっているので、単純計算で一手あたり約0.0033秒（300分の1秒）であり64段には約19億年かかる計算になる。だいぶマシになったがそれでも長い。

関連動画

関連リンク

• ハノイの塔100段のゴールまでの最短時間を計算してみた - 3枚から8枚まで遊べる。解答あり。

関連項目

• パズル
• 再帰
• ハノイ - ベトナムの首都。
• 井藤ノノハ - アニメ『ファイ・ブレイン ～神のパズル』の登場人物。ハノイの塔が名前の由来。
• ハノイの騎士 - アニメ『遊☆戯☆王ヴレインズ』の組織。ハノイの塔が名前の由来と思われ、作中でもハノイの塔が紹介されている。