ハノイの塔は、プログラミングで「再帰(さいき)」を学ぶときに、必ずといってよいほど出てくる題材です。手で解くと何百手もかかるのに、プログラムにすると数行で書けてしまう。その仕組みを、順に見ていきましょう。棒は左・中央・右、円盤には小さい順に1、2、3…と番号を付けます。
再帰とは
再帰とは、ある問題を解く手順の中で、同じ手順をもっと小さな問題に使うことです。小さくしていくと、いつかすぐ答えの分かる問題(円盤0枚なら何もしない、など)にたどり着くので、そこで止まります。
ハノイの塔を再帰で考える
n枚の塔を、左から右へ移すことを考えます。
- 上のn−1枚を、左から中央へ移す。
- いちばん大きい円盤nを、左から右へ動かす。
- 中央のn−1枚を、右へ移す。
1と3は「n−1枚の塔を移す」問題で、元の問題と同じ形をしています。違うのは、どの棒からどの棒へ移すかだけです。そこで、「n枚を、ある棒から別の棒へ、残りの棒を使って移す」という手順を1つ作れば、その中で自分自身を呼び出せます。
疑似コード
手順 hanoi(n, 移す元, 移す先, 使う棒):
もし n が 0 なら、何もしないで終わる
hanoi(n − 1, 移す元, 使う棒, 移す先) … 上のn−1枚をどかす
円盤 n を 移す元 から 移す先 へ動かす
hanoi(n − 1, 使う棒, 移す先, 移す元) … n−1枚を戻す
hanoi(3, 左, 右, 中央) で、3枚を左から右へ移す手順が出る これだけで、何枚でも最少手数の手順が出てきます。実際に動くPythonやC言語のコードは、Python・C言語でハノイの塔を解くで紹介しています。
呼び出しの広がり方
3枚のとき、hanoi がどのように呼び出されるかを書き出すと、次のような木の形になります。字下げが深いほど、内側の呼び出しです。
hanoi(3, 左→右)
├─ hanoi(2, 左→中央)
│ ├─ hanoi(1, 左→右) … 1を右へ
│ ├─ 2を中央へ
│ └─ hanoi(1, 右→中央) … 1を中央へ
├─ 3を右へ
└─ hanoi(2, 中央→右)
├─ hanoi(1, 中央→左) … 1を左へ
├─ 2を右へ
└─ hanoi(1, 左→右) … 1を右へ 上から順に読んだ「動かす」の並びが、そのまま7手の答えになっています。1回の呼び出しが、内側で2回の呼び出しを生むので、枚数が1増えるごとに仕事はほぼ2倍になります。
計算量
| 調べること | n枚のとき |
|---|---|
| 動かす回数(手数) | 2ⁿ−1回 |
| hanoi を呼び出す回数(0枚の呼び出しも数える) | 2ⁿ⁺¹−1回 |
| 呼び出しの深さ(同時に覚えておく量) | n+1段 |
手数が2ⁿ−1回になる理由は、最少手数の公式で証明しています。かかる時間は円盤の枚数に対して指数関数的に増え(O(2ⁿ))、覚えておく量は枚数に比例するだけ(O(n))です。手数そのものが2ⁿ−1回あるので、どんなに工夫しても、手順を全部書き出すにはこれだけの時間がかかります。
再帰を使わない解き方
再帰を使わずに、繰り返しだけで解く方法もあります。解き方の記事で紹介した、手で解くときの手順そのものです。
手順 hanoi_loop(n):
1 の向きを決める(n が奇数なら 左→右→中央、偶数なら 左→中央→右 の順)
手 = 1, 2, 3, … , 2ⁿ − 1 について繰り返す:
手 が奇数なら、円盤 1 を決めた向きに1本となりへ動かす
手 が偶数なら、1 が載っていない2本のいちばん上どうしを比べ、
小さいほうを大きいほう(または空の棒)へ動かす 再帰のように呼び出しを覚えておく必要がないので、使う記憶はとても少なくて済みます。
2進数で、何手目でも直接求める
さらに、何手目に何をするかを、それまでの手をたどらずに直接求める方法もあります。棒を0・1・2と番号で呼び、m手目(1から数える)について、
- 動かす円盤は、mを2進数で書いたときの末尾に並ぶ0の個数+1番の円盤。
- 動かす元の棒は、(m AND (m − 1)) を3で割った余り。
- 動かす先の棒は、((m OR (m − 1)) + 1) を3で割った余り。
AND・ORは、2進数の桁ごとの「かつ」「または」の計算です。たとえば m = 4(2進数で100)なら、末尾の0が2個なので円盤は3番、元は (4 AND 3) = 0 で棒0、先は ((4 OR 3) + 1) = 8 で、8を3で割った余りの棒2です。
この式で出てくる手順は、円盤が奇数枚なら棒0から棒2へ、偶数枚なら棒0から棒1へ移す手順になります。偶数枚で棒2へ移したいときは、棒1と棒2を入れ替えて読みます。手数と2進数のこうしたつながりは、規則性の記事でくわしく紹介しています。
