12.4 ハノイの塔の問題¶
マージソートや二分木の構築では、いずれも元の問題を元問題の半分の規模をもつ 2 つの部分問題に分解していました。しかし、ハノイの塔の問題では、異なる分解戦略を採用します。
Question
3 本の柱があり、それぞれを A、B、C とします。初期状態では、柱 A に \(n\) 枚の円盤が通されており、上から下へ小さい順に並んでいます。私たちの課題は、この \(n\) 枚の円盤を柱 C に移し、元の順序を保つことです（以下の図のとおり）。円盤を移動する際には、次のルールに従う必要があります。
- 円盤は 1 本の柱の頂上から取り出し、別の柱の頂上に置くことしかできません。
- 1 回に移動できる円盤は 1 枚だけです。
- 小さい円盤は常に大きい円盤の上になければなりません。
図 12-10 ハノイの塔の問題の例
規模が \(i\) のハノイの塔の問題を \(f(i)\) と表します 。たとえば \(f(3)\) は、\(3\) 枚の円盤を A から C へ移動するハノイの塔の問題を表します。
1. 基本ケースを考える¶
以下の図に示すように、問題 \(f(1)\) 、すなわち円盤が 1 枚だけの場合は、それを A から C へ直接移動すれば済みます。
図 12-11 規模 1 の問題の解
以下の図に示すように、問題 \(f(2)\) 、すなわち円盤が 2 枚ある場合は、小さい円盤が常に大きい円盤の上にある条件を満たすため、B を借りて移動を行う必要があります。
- まず上の小さい円盤を
AからBへ移します。 - 次に大きい円盤を
AからCへ移します。 - 最後に小さい円盤を
BからCへ移します。
図 12-12 規模 2 の問題の解
問題 \(f(2)\) を解く過程は、**2 枚の円盤を B を介して A から C へ移す**と要約できます。このとき、C を目標の柱、B を補助の柱と呼びます。
2. 部分問題への分解¶
問題 \(f(3)\) 、すなわち円盤が 3 枚ある場合になると、状況はやや複雑になります。
\(f(1)\) と \(f(2)\) の解が既知なので、分割統治の観点から、A の上部にある 2 枚の円盤をひとまとまりとみなして、次の図の手順を実行できます。こうして 3 枚の円盤を A から C へ順調に移動できます。
Bを目標の柱、Cを補助の柱として、2 枚の円盤をAからBへ移します。Aに残った 1 枚の円盤をAからCへ直接移動します。Cを目標の柱、Aを補助の柱として、2 枚の円盤をBからCへ移します。
図 12-13 規模 3 の問題の解
本質的には、問題 \(f(3)\) を 2 つの部分問題 \(f(2)\) と 1 つの部分問題 \(f(1)\) に分けています 。この 3 つの部分問題を順に解けば、元の問題も解決されます。これは、部分問題が独立しており、解を組み合わせられることを示しています。
ここまでで、次の図に示すハノイの塔の問題を解く分割統治戦略をまとめられます。元の問題 \(f(n)\) を 2 つの部分問題 \(f(n-1)\) と 1 つの部分問題 \(f(1)\) に分け、次の順序でこの 3 つの部分問題を解きます。
- \(n-1\) 枚の円盤を
Cを介してAからBへ移します。 - 残り \(1\) 枚の円盤を
AからCへ直接移します。 - \(n-1\) 枚の円盤を
Aを介してBからCへ移します。
この 2 つの部分問題 \(f(n-1)\) は、同じ方法で再帰的に分割できます。最小の部分問題 \(f(1)\) に到達するまでこれを続けます。一方、\(f(1)\) の解は既知であり、1 回の移動操作だけで済みます。
図 12-14 ハノイの塔の問題を解く分割統治戦略
3. コードの実装¶
コードでは、再帰関数 dfs(i, src, buf, tar) を定義します。その役割は、柱 src の上部にある \(i\) 枚の円盤を、補助の柱 buf を使って目標の柱 tar へ移動することです：
hanota.py
def move(src: list[int], tar: list[int]):
"""円盤を 1 枚移動"""
# src の上から円盤を1枚取り出す
pan = src.pop()
# 円盤を tar の上に置く
tar.append(pan)
def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
"""ハノイの塔の問題 f(i) を解く"""
# src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if i == 1:
move(src, tar)
return
# 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf)
# 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar)
# 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar)
def solve_hanota(A: list[int], B: list[int], C: list[int]):
"""ハノイの塔を解く"""
n = len(A)
# A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C)
hanota.cpp
/* 円盤を 1 枚移動 */
void move(vector<int> &src, vector<int> &tar) {
// src の上から円盤を1枚取り出す
int pan = src.back();
src.pop_back();
// 円盤を tar の上に置く
tar.push_back(pan);
}
/* ハノイの塔の問題 f(i) を解く */
void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
int n = A.size();
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.java
/* 円盤を 1 枚移動 */
void move(List<Integer> src, List<Integer> tar) {
// src の上から円盤を1枚取り出す
Integer pan = src.remove(src.size() - 1);
// 円盤を tar の上に置く
tar.add(pan);
}
/* ハノイの塔の問題 f(i) を解く */
void dfs(int i, List<Integer> src, List<Integer> buf, List<Integer> tar) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
void solveHanota(List<Integer> A, List<Integer> B, List<Integer> C) {
int n = A.size();
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.cs
/* 円盤を 1 枚移動 */
void Move(List<int> src, List<int> tar) {
// src の上から円盤を1枚取り出す
int pan = src[^1];
src.RemoveAt(src.Count - 1);
// 円盤を tar の上に置く
tar.Add(pan);
}
/* ハノイの塔の問題 f(i) を解く */
void DFS(int i, List<int> src, List<int> buf, List<int> tar) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
Move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
DFS(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
Move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
DFS(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
void SolveHanota(List<int> A, List<int> B, List<int> C) {
int n = A.Count;
// A の上から n 枚の円盤を B を介して C へ移す
DFS(n, A, B, C);
}
hanota.go
/* 円盤を 1 枚移動 */
func move(src, tar *list.List) {
// src の上から円盤を1枚取り出す
pan := src.Back()
// 円盤を tar の上に置く
tar.PushBack(pan.Value)
// `src` の最上部の円盤を取り外す
src.Remove(pan)
}
/* ハノイの塔の問題 f(i) を解く */
func dfsHanota(i int, src, buf, tar *list.List) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if i == 1 {
move(src, tar)
return
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfsHanota(i-1, src, tar, buf)
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar)
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfsHanota(i-1, buf, src, tar)
}
/* ハノイの塔を解く */
func solveHanota(A, B, C *list.List) {
n := A.Len()
// A の上から n 枚の円盤を B を介して C へ移す
dfsHanota(n, A, B, C)
}
hanota.swift
/* 円盤を 1 枚移動 */
func move(src: inout [Int], tar: inout [Int]) {
// src の上から円盤を1枚取り出す
let pan = src.popLast()!
// 円盤を tar の上に置く
tar.append(pan)
}
/* ハノイの塔の問題 f(i) を解く */
func dfs(i: Int, src: inout [Int], buf: inout [Int], tar: inout [Int]) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if i == 1 {
move(src: &src, tar: &tar)
return
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i: i - 1, src: &src, buf: &tar, tar: &buf)
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src: &src, tar: &tar)
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i: i - 1, src: &buf, buf: &src, tar: &tar)
}
/* ハノイの塔を解く */
func solveHanota(A: inout [Int], B: inout [Int], C: inout [Int]) {
let n = A.count
// リストの末尾が柱の上端に対応する
// src の上から n 個の円盤を、B を介して C に移動する
dfs(i: n, src: &A, buf: &B, tar: &C)
}
hanota.js
/* 円盤を 1 枚移動 */
function move(src, tar) {
// src の上から円盤を1枚取り出す
const pan = src.pop();
// 円盤を tar の上に置く
tar.push(pan);
}
/* ハノイの塔の問題 f(i) を解く */
function dfs(i, src, buf, tar) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i === 1) {
move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
function solveHanota(A, B, C) {
const n = A.length;
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.ts
/* 円盤を 1 枚移動 */
function move(src: number[], tar: number[]): void {
// src の上から円盤を1枚取り出す
const pan = src.pop();
// 円盤を tar の上に置く
tar.push(pan);
}
/* ハノイの塔の問題 f(i) を解く */
function dfs(i: number, src: number[], buf: number[], tar: number[]): void {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i === 1) {
move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
function solveHanota(A: number[], B: number[], C: number[]): void {
const n = A.length;
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.dart
/* 円盤を 1 枚移動 */
void move(List<int> src, List<int> tar) {
// src の上から円盤を1枚取り出す
int pan = src.removeLast();
// 円盤を tar の上に置く
tar.add(pan);
}
/* ハノイの塔の問題 f(i) を解く */
void dfs(int i, List<int> src, List<int> buf, List<int> tar) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
move(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
void solveHanota(List<int> A, List<int> B, List<int> C) {
int n = A.length;
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.rs
/* 円盤を 1 枚移動 */
fn move_pan(src: &mut Vec<i32>, tar: &mut Vec<i32>) {
// src の上から円盤を1枚取り出す
let pan = src.pop().unwrap();
// 円盤を tar の上に置く
tar.push(pan);
}
/* ハノイの塔の問題 f(i) を解く */
fn dfs(i: i32, src: &mut Vec<i32>, buf: &mut Vec<i32>, tar: &mut Vec<i32>) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if i == 1 {
move_pan(src, tar);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move_pan(src, tar);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar);
}
/* ハノイの塔を解く */
fn solve_hanota(A: &mut Vec<i32>, B: &mut Vec<i32>, C: &mut Vec<i32>) {
let n = A.len() as i32;
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C);
}
hanota.c
/* 円盤を 1 枚移動 */
void move(int *src, int *srcSize, int *tar, int *tarSize) {
// src の上から円盤を1枚取り出す
int pan = src[*srcSize - 1];
src[*srcSize - 1] = 0;
(*srcSize)--;
// 円盤を tar の上に置く
tar[*tarSize] = pan;
(*tarSize)++;
}
/* ハノイの塔の問題 f(i) を解く */
void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
move(src, srcSize, tar, tarSize);
return;
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, srcSize, tar, tarSize);
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
}
/* ハノイの塔を解く */
void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
// A の上から n 枚の円盤を B を介して C へ移す
dfs(*ASize, A, ASize, B, BSize, C, CSize);
}
hanota.kt
/* 円盤を 1 枚移動 */
fun move(src: MutableList<Int>, tar: MutableList<Int>) {
// src の上から円盤を1枚取り出す
val pan = src.removeAt(src.size - 1)
// 円盤を tar の上に置く
tar.add(pan)
}
/* ハノイの塔の問題 f(i) を解く */
fun dfs(i: Int, src: MutableList<Int>, buf: MutableList<Int>, tar: MutableList<Int>) {
// src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if (i == 1) {
move(src, tar)
return
}
// 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf)
// 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar)
// 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar)
}
/* ハノイの塔を解く */
fun solveHanota(A: MutableList<Int>, B: MutableList<Int>, C: MutableList<Int>) {
val n = A.size
// A の上から n 枚の円盤を B を介して C へ移す
dfs(n, A, B, C)
}
hanota.rb
### 円盤を1枚移動 ###
def move(src, tar)
# src の上から円盤を1枚取り出す
pan = src.pop
# 円盤を tar の上に置く
tar << pan
end
### ハノイの塔 f(i) を解く ###
def dfs(i, src, buf, tar)
# src に円盤が 1 枚だけ残っている場合は、そのまま tar へ移す
if i == 1
move(src, tar)
return
end
# 部分問題 f(i-1)：src の上部 i-1 枚の円盤を tar を補助にして buf へ移す
dfs(i - 1, src, tar, buf)
# 部分問題 f(1)：src に残る 1 枚の円盤を tar に移す
move(src, tar)
# 部分問題 f(i-1)：buf の上部 i-1 枚の円盤を src を補助にして tar へ移す
dfs(i - 1, buf, src, tar)
end
### ハノイの塔を解く ###
def solve_hanota(_A, _B, _C)
n = _A.length
# A の上から n 枚の円盤を B を介して C へ移す
dfs(n, _A, _B, _C)
end
コードの可視化
以下の図に示すように、ハノイの塔の問題は高さ \(n\) の再帰木を形成し、各ノードは 1 つの部分問題、すなわち 1 つ起動された dfs() 関数に対応します。したがって時間計算量は \(O(2^n)\) 、空間計算量は \(O(n)\) です。
図 12-15 ハノイの塔の問題の再帰木
Quote
ハノイの塔の問題は古い伝説に由来します。古代インドのある寺院で、僧侶たちは 3 本の高いダイヤモンドの柱と、\(64\) 枚の大きさの異なる金の円盤を持っていました。僧侶たちは絶えず円盤を動かし、最後の 1 枚が正しく置かれた瞬間に世界が終わると信じていました。
しかし、たとえ僧侶たちが 1 秒に 1 回移動するとしても、合計でおよそ \(2^{64} \approx 1.84×10^{19}\) 秒、約 \(5850\) 億年が必要で、現在推定されている宇宙の年齢をはるかに上回ります。したがって、この伝説が本当だったとしても、世界の終わりを心配する必要はなさそうです。