【C言語】再帰関数でハノイの塔を解くプログラムの書き方

ハノイの塔（Tower of Hanoi）は、フランスの数学者エドゥアール・リュカが考案したとされる有名な数学パズルです。3本の棒と、大きさの異なる複数の円盤を使用し、円盤はどの棒にも自由に差し込める構造になっています。初期状態では、1本の棒に円盤が小さいものが一番上になるよう昇順にきれいに積み重ねられており、この同じ積み方を3本目の棒で再現することがゴールとなります。

パズルの目的は、以下のシンプルなルールを守りながら、円盤の山全体を別の棒へ移動させることです。

• 一度に動かせるのは1枚の円盤のみ。
• 移動とは、ある山の一番上の円盤を取り、別の山の一番上に載せることを意味します。つまり、各山の最上部にある円盤しか動かせません。
• 小さい円盤の上に大きい円盤を置くことは禁止です。

実行例

入力： 3（円盤の枚数）

出力：

A to B
A to C
B to C
A to B
C to A
C to B
A to B

これは、棒Aに積まれた3枚の円盤すべてを、最小手数で棒Bへ移動させる手順を表しています。

C言語によるサンプルコード

以下は、再帰関数を使ってハノイの塔を解くC言語プログラムの例です。

#include <stdio.h>

void TOH(int n, char x, char y, char z) {
    if (n > 0) {
        TOH(n - 1, x, z, y);
        printf("\n%c to %c", x, y);
        TOH(n - 1, z, y, x);
    }
}

int main() {
    int n = 3;
    TOH(n, 'A', 'B', 'C');
    return 0;
}

出力結果

A to B
A to C
B to C
A to B
C to A
C to B
A to B

プログラムの解説

このプログラムの中核となるのが TOH 関数です。引数はそれぞれ、n（移動する円盤の枚数）、x（移動元）、y（移動先）、z（補助用の棒）を表しています。処理の流れは次のとおりです。

1. n-1枚の円盤を、移動元の棒xから補助棒zへ移動させる（TOH(n-1, x, z, y)）。
2. 残った一番大きな円盤を、棒xから目的地の棒yへ直接移動させる（printfで手順を出力）。
3. 補助棒zに退避しておいたn-1枚の円盤を、棒yへ移動させる（TOH(n-1, z, y, x)）。

このように「n枚の問題」を「n-1枚の問題」に分解していく再帰的なアプローチにより、コードは非常にシンプルになります。なお、ハノイの塔の最小移動回数は 2ⁿ − 1 回であることが知られており、円盤3枚の場合は 2³ − 1 = 7回の出力となっていることが確認できます。