ハノイの塔を解くプログラムを、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回かを確かめると安心です。