ハノイの塔問題とは？再帰アルゴリズムの考え方とC++実装例をわかりやすく解説

ハノイの塔（Tower of Hanoi）は、コンピュータサイエンスの教育現場でも古くから親しまれている古典的なパズル問題です。3本の棒（杭）と n 枚の円盤を使って遊びます。最初はすべての円盤が1本目の棒（始点）に積まれており、これらすべての円盤を3本目の棒（目的）へ移動させるのが目標です。途中、2本目の棒は補助用として自由に使えます。

ハノイの塔のルール

円盤を移動する際には、次の3つのルールを守る必要があります。

• 1回の移動で動かせるのは、1枚の円盤だけ
• 棒から取り出せるのは、最上部にある円盤のみ
• 大きい円盤を小さい円盤の上に載せることは禁止

再帰を使った解法の考え方

この問題は再帰（リカージョン）を使うと非常にシンプルに解くことができます。考え方は以下の3ステップです。

1. まず再帰呼び出しにより、上から (n-1) 枚の円盤を始点の棒から補助の棒へ移動させる。
2. 残った一番大きい円盤（n枚目）を、始点の棒から目的の棒へ移動させる。
3. 再度再帰呼び出しにより、(n-1) 枚の円盤を補助の棒から目的の棒へ移動させる。

この操作を再帰的に繰り返すことで、任意の枚数の円盤を正しい手順で移動できます。なお、ハノイの塔の最小移動回数は 2ⁿ − 1 回であることが知られています。たとえば円盤が3枚なら、最小で7回の移動が必要です。

入力と出力

Input:
Number of discs: 3
Output:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

アルゴリズム

関数のシグネチャは次のとおりです。

toh(n, s, a, d)

入力： 円盤の枚数 n、始点の棒 s、補助の棒 a、目的の棒 d。

出力： ルールを守りながら、すべての円盤を始点から目的の棒へ移動させるための手順。

擬似コードは以下のようになります。

Begin
   if n = 1, then
      display move disc from s to d
   toh(n-1, s, d, a)

   display move disc from s to d
   toh(n-1, a, s, d)
End

C++による実装例

実際にC++で実装すると、次のようになります。静的変数 count を使うことで、移動手順に連番を付けて表示しています。

#include<iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
   static int count = 0;        // 移動回数を記録するカウンタ
   if(n == 1) {
      count++;
      cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
      return;     // ベースケース：円盤が1枚のとき
   }

   TOH(n-1, s, d, a);           // 再帰呼び出し：(n-1)枚を補助棒へ
   count++;
   cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
   TOH(n-1, a, s, d);           // 再帰呼び出し：(n-1)枚を目的棒へ
}

int main() {
   int n;
   cout << "Enter the number of disks: ";
   cin >> n;
   TOH(n, 'A', 'B', 'C');
}

実行結果

円盤の枚数として「3」を入力した場合の実行結果は次のとおりです。移動回数が7回（= 2³ − 1）になっていることが確認できます。

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

まとめ

ハノイの塔は、再帰処理の仕組みを直感的に理解できる絶好の題材です。「(n-1)枚を一旦退避させる → 最大の円盤を移す → (n-1)枚を戻す」という分割統治の発想は、他の多くのアルゴリズムにも応用されています。ぜひ自分でもコードを書いて、円盤の枚数を変えながら動作を確かめてみてください。