C言語でハノイの塔の解法プログラムを実装!

ハノイの塔はプログラミングで再帰処理(再帰呼び出し)を学ぶのに最適なパズルです。再帰処理ははっきり言って難しいですが、ハノイの塔なら割と楽しくプログラミングに取り組めますので、再帰処理について学びたいのであればプログラミングしてみることをオススメします。

このページではハノイの塔とその解き方(最短手順での解き方)、ハノイの塔を解くプログラムについて解説します。

ハノイの塔

ハノイの塔というのは左の杭に積み重ねられた全ての円盤を、下記の3つのルールを満たしながら中央の杭に移動させるパズルです。

  • 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
  • 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
  • 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

引用元:Wikipedia

分かりやすいように図を使って説明します。最初の状態では左の杭に全ての円盤が積み重ねられています。

ハノイの塔の最初の状態

で、目指すのは下のように中央の杭に全ての円盤が積み重ねられる状態です。

ハノイの塔の最終状態

右の杭は自由に使用して良いですが、円盤は1枚ずつしか移動できません。

ハノイの塔禁止事項1

円盤は杭の一番上のものしか移動させることができません。

ハノイの塔禁止事項2

また円盤は杭の上側からしか積み重ねることができません。

ハノイの塔禁止事項2

さらに円盤の上にはその円盤よりも大きい円盤を積むことはできません。

ハノイの塔禁止事項3

これらの状態をルールを守りながら中央の杭に全ての円盤を積み重ねることを目的としたパズルになります。

ハノイの塔の解き方

続いてハノイの塔の解き方について解説します。

説明の中ではハノイの塔の3つの塔に名前をつけています。左の塔は最初に円盤が積み上げられている塔として “src” 、真ん中の塔は円盤の積み上げ先の塔として “dst”、右の塔は作業領域として使う塔として “work” という名前をつけています。

高さ1のハノイの塔の解き方

まずは高さ1のハノイの塔を解く方法について考えてみましょう。

高さ1のハノイの塔の初期状態

これは非常に簡単ですね。円盤を src から dst に移動させれば解くことができます。

高さ1のハノイの塔の最終状態

つまり高さ1のハノイの塔の解き方は下記となります。

  • src から dst へ円盤を移動

高さ2のハノイの塔の解き方

続いて高さ2のハノイの塔の解き方について解説します。

高さ2のハノイの塔の初期状態

高さ2のハノイの塔は下記の3回の円盤の移動で解くことができます。

  1. src から work へ円盤を移動
  2. src から dst へ円盤を移動
  3. work から dst へ円盤を移動

高さ2のハノイの塔の解き方

ここで注目していただきたいのが 1. の処理です。高さ1なので直感的に分かりにくいかもしれませんが、src の一番大きい円盤の上の「高さ1の塔」が work に移動していることが分かります。

高さ1の塔の移動

つまり、これは一番大きい円盤の上にある「高さ1のハノイの塔」を dst と work を置き換えて解いているのと同じ処理と言えます。

これは、高さ1のハノイの塔の解き方が下記であり、

  • src から dst へ円盤を移動

高さ2のハノイの塔を解く時の 1. の処理が下記であることからも確認できると思います。dst が work へ置き換わっただけですよね。

  1. src から work へ円盤を移動

つまり 1. の処理は下記のように捉えることが可能です。

dst を work と置き換えて高さ1のハノイの塔を解く

1. の処理を行うと src に一番大きい円盤が残り、dst は空いている状態になります。ハノイの塔を解くためには dst の一番下には一番大きい円盤を置く必要がありますので、この dst が空いている隙に src から dst に円盤を移動させましょう。これが 2. の処理になります。

高さ2のハノイの塔で一番大きい円盤を移動させる様子

続いて 3. の処理を見てみましょう。3. の処理を実行すると、work にある高さ1の塔が dst の一番大きい円盤の上に移動することになります。

高さ1の塔の移動2

これは「高さ1のハノイの塔」を src と work を置き換えて解いているのと同じ処理と言えます。

これは、高さ1のハノイの塔の解き方は下記で、

  • src から dst へ円盤を移動

高さ2のハノイの塔を解く時の 3. の処理が下記であることからも確認できると思います。src が work へ置き換わっただけですよね。

  1. work から dst へ円盤を移動

つまり 3. の処理は下記のように捉えることが可能です。

src を work と置き換えて高さ1のハノイの塔を解く

したがって高さ2のハノイの塔は下記の3つの処理で解くことができます。

  1. dst を work と置き換えて高さ1のハノイの塔を解く
  2. src から dst へ円盤を移動
  3. src を work と置き換えて高さ1のハノイの塔を解く

高さ3のハノイの塔の解き方

次は高さ3のハノイの塔の解き方について解説します。

高さ3のハノイの塔の初期状態

高さ3のハノイの塔は下記の7回の円盤の移動で解くことができます。

  1. src から dst へ円盤を移動
  2. src から work へ円盤を移動
  3. dst から work へ円盤を移動
  4. src から dst へ円盤を移動
  5. work から src へ円盤を移動
  6. work から dst へ円盤を移動
  7. src から dst へ円盤を移動

高さ3のハノイの塔の解法

まず注目していただきたいのが 1. 2. 3. の処理です。1. 2. 3. の処理を実行すると src の高さ2の塔が work に移動させられることになります。つまりこれは、dst と work を置き換えて高さ2のハノイの塔を解いている処理と言えます。

高さ2の塔の移動1

これは、高さ2のハノイの塔を解く処理が下記で、

  1. src から work へ円盤を移動
  2. src から dst へ円盤を移動
  3. work から dst へ円盤を移動

高さ3のハノイの塔を解く処理の 1. 2. 3. が下記であることからも確認できると思います。work と dst が置き換わっただけですよね。

  1. src から dst へ円盤を移動
  2. src から work へ円盤を移動
  3. dst から work へ円盤を移動

つまり、1. 2. 3. の処理は下記のように捉えることが可能です。

dst と work を置き換えて高さ2のハノイの塔を解く

1. 2. 3. を実行すると src には一番大きい円盤が残り、dst は空いている状態になります。ハノイの塔を解くには dst に一番大きい円盤を積む必要がありますので、空いている隙に src から dst に円盤を移動してします。これが 4. の処理になります。

高さ3のハノイの塔で一番大きい円盤を移動させる様子

5. 6. 7. の処理を実行すると work の高さ2の塔が dst の一番大きい円盤の上に移動させられることになります。つまりこれは、src と work を置き換えて高さ2のハノイの塔を解いている処理と言えます。

高さ2の塔の移動2

これについても、高さ2のハノイの塔を解く処理が下記で、

  1. src から work へ円盤を移動
  2. src から dst へ円盤を移動
  3. work から dst へ円盤を移動

高さ3のハノイの塔を解く処理の 5. 6. 7. が下記であることからも確認できると思います。 work と src が置き換わっただけです。

  1. work から src へ円盤を移動
  2. work から dst へ円盤を移動
  3. src から dst へ円盤を移動

つまり 5. 6. 7. の処理は下記のように捉えることが可能です。

src を work を置き換えて高さ2のハノイの塔を解く

したがって高さ3のハノイの塔は下記の3つの処理で解くことができます。

  1. dst を work を置き換えて高さ2のハノイの塔を解く
  2. src から dst へ移動
  3. src を work を置き換えて高さ2のハノイの塔を解く

高さ N のハノイの塔の解き方

高さ N のハノイの塔の解き方を解説するために、まず高さ2と高さ3のハノイの塔の解き方を再掲します。

高さ2のハノイの塔の解き方

  1. dst を work と置き換えて高さ1のハノイの塔を解く
  2. src から dst へ円盤を移動
  3. src を work と置き換えて高さ1のハノイの塔を解く

高さ3のハノイの塔の解き方

  1. dst を work を置き換えて高さ2のハノイの塔を解く
  2. src から dst へ移動
  3. src を work を置き換えて高さ2のハノイの塔を解く

ポイントは両方とも「高さ – 1 のハノイの塔を解くこと」を利用している点ですね。この「高さ – 1 のハノイの塔を解くこと」を利用すれば、実は同様の方法でどんな高さのハノイの塔も下記の方法で解くことが可能です。

高さを N とした時のハノイの塔の解き方は下記の通りです。

  1. dst を work を置き換えて高さ N -1 のハノイの塔を解く
  2. src から dst へ移動
  3. src を work を置き換えて高さ N -1 のハノイの塔を解く

1. の処理により src の一番大きい円盤を除いた高さ N – 1 の塔が work に移動し、一番大きい円盤のみが src に残ります。

ハノイの塔の前半処理終了後の状態

あとは 2. により一番大きい円盤を src から dst へ移し、dst へ移った一番大きい円盤の上に 3. により高さ N – 1 の塔を dst に移動させれば、高さ N のハノイの塔を解くことができます。

高さ N – 1 のハノイの塔を解く際には高さ N – 2 のハノイの塔を解く処理が行われます。さらに高さ N – 2 のハノイの塔を解く際には高さ N – 3 の処理が行われます。これが高さ 1 になるまで繰り返し実行されることになります。

再帰処理が実行される様子

一見、3つの処理だけでハノイの塔が解けるので簡単そうに見えますが、実は再帰処理により複雑な処理が実行されることになります。

スポンサーリンク

ハノイの塔のプログラム実装のポイント

ハノイの塔の解き方が分かったところで、実際のハノイの塔を解くプログラムを作成していきたいと思います。まずはプログラム作成のためのポイント部分を解説します。

塔の状態

ハノイの塔の解法プログラムを作成するためには、まずは各塔にどの円盤が積まれているかの状態を管理するためのデータを用意します。

塔の数を NUM (塔は src と dst と work なので3本なので NUM は必ず3)、塔の高さを HEIGHT とした場合、下のような2次元データで表現することが可能です。

塔を表すデータ

データの右端が塔の一番下で、右端から左側に順に円盤が積み重なっていくことになります。また、格納される値は円盤の大きさを表します。 – 1 は円盤が無い状態を表すことにしています。

例えば高さ4のハノイの塔の最初の状態は下のようになります。

高さ4のデータの例

このデータを次に説明する円盤の移動により変化させながら、最終的に dst に全ての円盤を移動させます。

円盤の移動

ハノイの塔の解法プログラムを作成するためには、円盤を他の塔に移動させる処理が必要になります。

ハノイの塔ではルール上、円盤は積み重なっているものの一番上のものを移動する必要があります。そしてそれを他の塔の円盤の一番上に積み重ねます。

円盤の移動の様子

イメージとしてはスタックの POP と PUSH ですね。一番上のデータを取り出す、一番上にデータを追加する、というところはまさに同じ処理になります。

スタックについて知りたい方は下のページで解説していますのでこちらを参考にしてください。

【データ構造】スタックとキューをC言語で実装

このページで紹介するプログラムでは円盤を移動する関数を move 関数として定義しています。第一引数に塔の状態を表すデータへのポインタ、第二引数に移動元の塔の行番号、第三引数に移動先の塔の行番号を指定することができ、実行することで第一引数の塔の状態を表すデータの移動元の行の円盤が移動先の行に移動します。つまり第一引数で指定したデータの中身が変わります。

ハノイの塔を解く関数

ハノイの塔の解法を行う関数は下記をそのまま実装すれば良いです。

  1. dst を work を置き換えて高さ N -1 のハノイの塔を解く
  2. src から dst へ移動
  3. src を work を置き換えて高さ N -1 のハノイの塔を解く

このページで紹介するソースコードでは、ハノイの塔を解く関数名を hanoi_func とし、引数としては「塔の状態を表すデータ(へのポインタ)」「塔の高さ」「src とする行番号」「dst とする行番号」「work とする行番号」を指定できるようにしています。

ですので、上記の3つの処理は下記のように記述することができます。

hanoi_func(tower, height - 1, src, work, dst);
move(tower, src, dst);
hanoi_func(tower, height - 1, work, src, dst);

tower は塔の状態で解説した3つの塔の状態を表すデータへのポインタで、move は円盤の移動で解説した円盤を移動する関数になります。

src, dst, work はそれぞれ 0, 1, 2 に enum により名前をつけたものです。

height を 1 減らし、src や work, dst を入れ替えて hanoi_func を実行することで高さを1減らしたハノイの塔を解くことができます。

ハノイの塔の解法プログラム

最後にハノイの塔の解法プログラムの全体を載せておきます。

#include <stdio.h>
#include <stdlib.h>

/* 塔の高さ */
#define HEIGHT 6

/* 塔の本数(3固定) */
#define NUM 3

/* 塔に名前をつける */
typedef enum {
  src = 0,
  dst,
  work
} type;

void move(int **, type, type);
int pop(int **, type);
void push(int **, type, int);
void print_hanoi(int **);
void print_hanoi_debug(int **);
void hanoi_func(int **, int, type, type, type);

/* 高さ height のハノイの塔を解く関数 */
void hanoi_func(int **tower, int height, type src, type dst, type work){

  if(height > 1){
    /* dst と work を置き換えて高さ height - 1のハノイの塔を解く */
    hanoi_func(tower, height - 1, src, work, dst);
  }

  /* 一番大きい円盤を空いている dst へ移動 */
  /* height が 1 の場合はこの処理のみを行う */
  move(tower, src, dst);

  if(height > 1){
    /* src と work を置き換えて高さ height - 1のハノイの塔を解く */
    hanoi_func(tower, height - 1, work, dst, src);
  }
}

/* 塔の状態を表示する関数 */
void print_hanoi(int **tower){
  int i, j, k;
  int max_space;
  int pre_space;
  int num_print;

  max_space = 2 * (HEIGHT + 1);

  for(j = 0; j < HEIGHT; j++){
    for(i = 0; i < NUM; i++){
      /* 空の場合はスペースのみを出力 */
      if(tower[i][j] == -1){
        for(k = 0; k < max_space; k++){
          printf(" ");
        }
      } else {
        /* 空でない場合は円盤の大きさ * 2 の数の # を出力 */
        num_print = 2 * tower[i][j];
        pre_space = (max_space - num_print) / 2;
        for(k = 0; k < pre_space; k++){
          printf(" ");
        }
        for(k = pre_space; k < pre_space + num_print; k++){
          printf("#");
        }
        for(k = pre_space + num_print; k < max_space; k++){
          printf(" ");
        }
      }
    }
    printf("\n");
  }
}

/* 塔の状態を表示する関数 */
void print_hanoi_debug(int **tower){
  char c;

  /* 塔の状態を表示 */
  print_hanoi(tower);

  /* プログラムをとめるための scanf */
  printf("Press Enter Key...");
  scanf("%c", &c);
}

/* s で指定された塔から d で指定された塔に円盤を移動する関数 */
void move(int **tower, type s, type d){
  int data;
  static int count = 1;

  /* デバッグ用の表示 */
  printf("move %d : %d -> %d\n", count, s, d);

  /* s の塔から円盤の大きさを取得し d の塔に移動 */
  data = pop(tower, s);
  push(tower, d, data);

  /* デバッグ用の表示 */
  print_hanoi_debug(tower);

  count++;
}

/* 指定された塔に指定された値を格納する関数 */
void push(int **tower, type s, int data){
  int i;

  /* 塔の一番下から空いている箇所を探す */
  for(i = HEIGHT - 1; i >= 0; i--){
    if(tower[s][i] == -1){
      break;
    }
  }

  tower[s][i] = data;
}

/* 指定された塔の一番上の円盤を取得する関数 */
int pop(int **tower, type s){
  int i;
  int ret;
  /* 円盤のある箇所を塔の一番上から探す */
  for(i = 0; i < HEIGHT; i++){
    if(tower[s][i] != -1){
      break;
    }
  }

  /* 塔の一番上のデータを取得 */
  ret = tower[s][i];

  /* 取得された箇所は空に */
  tower[s][i] = -1
  ;
  return ret;
}

int main(void){
  int **tower;
  int i;

  /* 塔の状態を格納するデータのためのメモリ取得 */
  tower = (int**)malloc(sizeof(int*) * NUM);
  for(i = 0; i < NUM; i++){
    tower[i] = (int*)malloc(sizeof(int) * HEIGHT);
  }

  /* ハノイの塔の初期状態を設定 */
  for(i = 0; i < HEIGHT; i++){
    /* src には塔の上から順に小さい円盤を積む */
    tower[src][i] = i + 1;

    /* dst と work は全て空 */
    tower[dst][i] = -1;
    tower[work][i] = -1;
  }

  /* 高さHEIGHTのハノイの塔を解く */
  hanoi_func(tower, HEIGHT, src, dst, work);

  /* 塔の状態を格納するデータを解放 */
  for(i = 0; i < NUM; i++){
    free(tower[i]);
  }
  free(tower);

  return 0;
}

割と長いソースコードになっていますが、1 / 3 くらいはデバッグ用に書いたものですので、ハノイの塔を解く処理自体のコードは短いです。

実行すると下のようにハノイの塔の途中処理結果を表示することが可能です。頑張って作ったのですが、スマホや表示するときのフォントによってはずれてしまうかもしれません…。

move 29 : 1 -> 0
                                          
                                          
                                          
                                ######    
      ##                       ########   
 ############      ####       ##########  
Press Enter Key...
move 30 : 1 -> 2
                                          
                                          
                                 ####     
                                ######    
      ##                       ########   
 ############                 ##########  
Press Enter Key...
move 31 : 0 -> 2
                                          
                                  ##      
                                 ####     
                                ######    
                               ########   
 ############                 ##########  
Press Enter Key...

ソースコード先頭付近の HEIGHT の定義を変更すればいろんな高さのハノイの塔を解くことが可能です。塔の状態がどんどん変わっていく様子が面白いと思いますので、是非試して見てください。

まとめ

今回はハノイの塔の解き方と、ハノイの塔を解くプログラムについて解説しました。再帰処理を使うと一見簡単そうに見えるソースコードで複雑な処理ができることを理解していただけたのではないかと思います。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です