ハノイの塔を解くプログラムを、PythonとC言語で書いてみます。どれも、円盤3枚を左の棒から右の棒へ移す手順を出力します。考え方はハノイの塔のアルゴリズムで説明しているので、ここではコードと動かし方を中心に紹介します。
Pythonで再帰を使って解く
いちばん基本の形です。「上のn−1枚をどかす → 円盤nを動かす → n−1枚を戻す」を、そのまま関数にします。
def hanoi(n, src, dst, via, moves):
if n == 0:
return
hanoi(n - 1, src, via, dst, moves) # 上のn-1枚をどかす
moves.append((n, src, dst)) # 円盤nを動かす
hanoi(n - 1, via, dst, src, moves) # n-1枚を戻す
moves = []
hanoi(3, "左", "右", "中央", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
print(f"{i}手目: {disc}を{src}から{dst}へ")
print(f"全部で{len(moves)}手") hanoi.py という名前で保存し、python3 hanoi.py で実行すると、次のように出力されます。
1手目: 1を左から右へ
2手目: 2を左から中央へ
3手目: 1を右から中央へ
4手目: 3を左から右へ
5手目: 1を中央から左へ
6手目: 2を中央から右へ
7手目: 1を左から右へ
全部で7手 hanoi(3, ...) の3を変えれば、何枚でも解けます。ただし手数は2ⁿ−1回なので、20枚で約100万手、30枚で約10億手と、すぐに膨大な量になります。Pythonは再帰の深さに上限(標準で1000段ほど)がありますが、ハノイの塔の再帰の深さは枚数+1段なので、問題になる前に手数のほうが多くなりすぎます。
Pythonで再帰を使わずに解く
手で解くときの手順(解き方の記事の2つの決まり)を、そのまま繰り返しで書く形です。棒は0(左)・1(中央)・2(右)の番号で扱います。
def hanoi_loop(n):
names = ["左", "中央", "右"]
pegs = [list(range(n, 0, -1)), [], []] # 下から上へ
order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2] # 1が回る順
pos = 0 # 1がいる棒(orderの何番目か)
moves = []
for m in range(1, 2 ** n):
if m % 2 == 1:
# 奇数回目: 1を決めた向きに1本となりへ
a = order[pos]
pos = (pos + 1) % 3
b = order[pos]
else:
# 偶数回目: 1が載っていない2本で、小さいほうを大きいほうへ
a, b = [p for p in range(3) if p != order[pos]]
if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
a, b = b, a
pegs[b].append(pegs[a].pop())
moves.append((pegs[b][-1], names[a], names[b]))
return moves
for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
print(f"{i}手目: {disc}を{src}から{dst}へ") 出力は、再帰の形とまったく同じ7手になります。1〜10枚のどの枚数でも、再帰の形と同じ手順が出ることを確かめています。
Pythonで2進数から直接求める
m手目に何をするかを、それまでの手をたどらずに計算する形です。式の意味はアルゴリズムの記事で説明しています。
def hanoi_bits(n):
for m in range(1, 2 ** n):
disc = (m & -m).bit_length() # 末尾の0の個数+1
src = (m & (m - 1)) % 3
dst = ((m | (m - 1)) + 1) % 3
yield disc, src, dst
print(list(hanoi_bits(3))) 実行すると [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)] と出ます。(円盤, 元の棒, 先の棒) の組で、上の7手と同じです。この式は、奇数枚なら棒0から棒2へ、偶数枚なら棒0から棒1へ移す手順を出すので、偶数枚を右へ移したいときは棒1と棒2を入れ替えて使います。
C言語で再帰を使って解く
C言語でも、形はPythonと同じです。
#include <stdio.h>
static int count = 0;
void hanoi(int n, const char *src, const char *dst, const char *via) {
if (n == 0) return;
hanoi(n - 1, src, via, dst);
count++;
printf("%d手目: %dを%sから%sへ\n", count, n, src, dst);
hanoi(n - 1, via, dst, src);
}
int main(void) {
hanoi(3, "左", "右", "中央");
printf("全部で%d手\n", count);
return 0;
} hanoi.c という名前で保存し、cc -o hanoi hanoi.c でコンパイルして ./hanoi で実行すると、Pythonの再帰の形と同じ7手と「全部で7手」が出力されます。文字列に日本語を使っているので、ファイルはUTF-8で保存してください。
書くときのつまずきどころ
- 引数の順番を取り違える: 1回目の呼び出しは「使う棒」と「移す先」を入れ替え、2回目は「移す元」と「使う棒」を入れ替えます。ここを間違えると、ルール違反の手が出ます。
- 止める条件を忘れる:
n == 0(またはn == 1)で止めないと、いつまでも呼び出し続けてしまいます。 - 確かめ方: 出てきた手順を盤に当てはめ、大きい円盤を小さい円盤の上に置く手がないか、手数が2ⁿ−1回かを確かめると安心です。
