ハノイの塔はプログラミングで再帰処理（再帰呼び出し）を学ぶのに最適なパズルです。再帰処理ははっきり言って難しいですが、ハノイの塔なら割と楽しくプログラミングに取り組めますので、再帰処理について学びたいのであればプログラミングしてみることをオススメします。
このページではハノイの塔とその解き方（最短手順での解き方）、ハノイの塔を解くプログラムについて解説します。
Contents
ハノイの塔
ハノイの塔というのは左の杭に積み重ねられた全ての円盤を、下記の３つのルールを満たしながら中央の杭に移動させるパズルです。
- 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
- 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
- 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
引用元：Wikipedia
分かりやすいように図を使って説明します。最初の状態では左の杭に全ての円盤が積み重ねられています。
で、目指すのは下のように中央の杭に全ての円盤が積み重ねられる状態です。
右の杭は自由に使用して良いですが、円盤は１枚ずつしか移動できません。
円盤は杭の一番上のものしか移動させることができません。
また円盤は杭の上側からしか積み重ねることができません。
さらに円盤の上にはその円盤よりも大きい円盤を積むことはできません。
これらの状態をルールを守りながら中央の杭に全ての円盤を積み重ねることを目的としたパズルになります。
ハノイの塔の解き方
続いてハノイの塔の解き方について解説します。
説明の中ではハノイの塔の３つの塔に名前をつけています。左の塔は最初に円盤が積み上げられている塔として “src” 、真ん中の塔は円盤の積み上げ先の塔として “dst”、右の塔は作業領域として使う塔として “work” という名前をつけています。
スポンサーリンク
高さ１のハノイの塔の解き方
まずは高さ１のハノイの塔を解く方法について考えてみましょう。
これは非常に簡単ですね。円盤を src から dst に移動させれば解くことができます。
つまり高さ１のハノイの塔の解き方は下記となります。
- src から dst へ円盤を移動
高さ２のハノイの塔の解き方
続いて高さ２のハノイの塔の解き方について解説します。
高さ２のハノイの塔は下記の３回の円盤の移動で解くことができます。
- src から work へ円盤を移動
- src から dst へ円盤を移動
- work から dst へ円盤を移動
ここで注目していただきたいのが 1. の処理です。高さ１なので直感的に分かりにくいかもしれませんが、src の一番大きい円盤の上の「高さ１の塔」が work に移動していることが分かります。
つまり、これは一番大きい円盤の上にある「高さ１のハノイの塔」を dst と work を置き換えて解いているのと同じ処理と言えます。
これは、高さ１のハノイの塔の解き方が下記であり、
- src から dst へ円盤を移動
高さ２のハノイの塔を解く時の 1. の処理が下記であることからも確認できると思います。dst が work へ置き換わっただけですよね。
- src から work へ円盤を移動
つまり 1. の処理は下記のように捉えることが可能です。
dst を work と置き換えて高さ１のハノイの塔を解く
1. の処理を行うと src に一番大きい円盤が残り、dst は空いている状態になります。ハノイの塔を解くためには dst の一番下には一番大きい円盤を置く必要がありますので、この dst が空いている隙に src から dst に円盤を移動させましょう。これが 2. の処理になります。
続いて 3. の処理を見てみましょう。3. の処理を実行すると、work にある高さ１の塔が dst の一番大きい円盤の上に移動することになります。
これは「高さ１のハノイの塔」を src と work を置き換えて解いているのと同じ処理と言えます。
これは、高さ１のハノイの塔の解き方は下記で、
- src から dst へ円盤を移動
高さ２のハノイの塔を解く時の 3. の処理が下記であることからも確認できると思います。src が work へ置き換わっただけですよね。
- work から dst へ円盤を移動
つまり 3. の処理は下記のように捉えることが可能です。
src を work と置き換えて高さ１のハノイの塔を解く
したがって高さ２のハノイの塔は下記の３つの処理で解くことができます。
- dst を work と置き換えて高さ１のハノイの塔を解く
- src から dst へ円盤を移動
- src を work と置き換えて高さ１のハノイの塔を解く
高さ３のハノイの塔の解き方
次は高さ３のハノイの塔の解き方について解説します。
高さ３のハノイの塔は下記の７回の円盤の移動で解くことができます。
- src から dst へ円盤を移動
- src から work へ円盤を移動
- dst から work へ円盤を移動
- src から dst へ円盤を移動
- work から src へ円盤を移動
- work から dst へ円盤を移動
- src から dst へ円盤を移動
まず注目していただきたいのが 1. 2. 3. の処理です。1. 2. 3. の処理を実行すると src の高さ２の塔が work に移動させられることになります。つまりこれは、dst と work を置き換えて高さ２のハノイの塔を解いている処理と言えます。
これは、高さ２のハノイの塔を解く処理が下記で、
- src から work へ円盤を移動
- src から dst へ円盤を移動
- work から dst へ円盤を移動
高さ３のハノイの塔を解く処理の 1. 2. 3. が下記であることからも確認できると思います。work と dst が置き換わっただけですよね。
- src から dst へ円盤を移動
- src から work へ円盤を移動
- dst から work へ円盤を移動
つまり、1. 2. 3. の処理は下記のように捉えることが可能です。
dst と work を置き換えて高さ２のハノイの塔を解く
1. 2. 3. を実行すると src には一番大きい円盤が残り、dst は空いている状態になります。ハノイの塔を解くには dst に一番大きい円盤を積む必要がありますので、空いている隙に src から dst に円盤を移動してします。これが 4. の処理になります。
5. 6. 7. の処理を実行すると work の高さ２の塔が dst の一番大きい円盤の上に移動させられることになります。つまりこれは、src と work を置き換えて高さ２のハノイの塔を解いている処理と言えます。
これについても、高さ２のハノイの塔を解く処理が下記で、
- src から work へ円盤を移動
- src から dst へ円盤を移動
- work から dst へ円盤を移動
高さ３のハノイの塔を解く処理の 5. 6. 7. が下記であることからも確認できると思います。 work と src が置き換わっただけです。
- work から src へ円盤を移動
- work から dst へ円盤を移動
- src から dst へ円盤を移動
つまり 5. 6. 7. の処理は下記のように捉えることが可能です。
src を work を置き換えて高さ２のハノイの塔を解く
したがって高さ３のハノイの塔は下記の３つの処理で解くことができます。
- dst を work を置き換えて高さ２のハノイの塔を解く
- src から dst へ移動
- src を work を置き換えて高さ２のハノイの塔を解く
スポンサーリンク
高さ N のハノイの塔の解き方
高さ N のハノイの塔の解き方を解説するために、まず高さ２と高さ３のハノイの塔の解き方を再掲します。
高さ２のハノイの塔の解き方
- dst を work と置き換えて高さ１のハノイの塔を解く
- src から dst へ円盤を移動
- src を work と置き換えて高さ１のハノイの塔を解く
高さ３のハノイの塔の解き方
- dst を work を置き換えて高さ２のハノイの塔を解く
- src から dst へ移動
- src を work を置き換えて高さ２のハノイの塔を解く
ポイントは両方とも「高さ – 1 のハノイの塔を解くこと」を利用している点ですね。この「高さ – 1 のハノイの塔を解くこと」を利用すれば、実は同様の方法でどんな高さのハノイの塔も下記の方法で解くことが可能です。
高さを N とした時のハノイの塔の解き方は下記の通りです。
- dst を work を置き換えて高さ N -1 のハノイの塔を解く
- src から dst へ移動
- 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 になるまで繰り返し実行されることになります。
一見、３つの処理だけでハノイの塔が解けるので簡単そうに見えますが、実は再帰処理により複雑な処理が実行されることになります。
ハノイの塔のプログラム実装のポイント
ハノイの塔の解き方が分かったところで、実際のハノイの塔を解くプログラムを作成していきたいと思います。まずはプログラム作成のためのポイント部分を解説します。
塔の状態
ハノイの塔の解法プログラムを作成するためには、まずは各塔にどの円盤が積まれているかの状態を管理するためのデータを用意します。
塔の数を NUM (塔は src と dst と work なので３本なので NUM は必ず３）、塔の高さを HEIGHT とした場合、下のような２次元データで表現することが可能です。
データの右端が塔の一番下で、右端から左側に順に円盤が積み重なっていくことになります。また、格納される値は円盤の大きさを表します。 – 1 は円盤が無い状態を表すことにしています。
例えば高さ４のハノイの塔の最初の状態は下のようになります。
このデータを次に説明する円盤の移動により変化させながら、最終的に dst に全ての円盤を移動させます。
スポンサーリンク
円盤の移動
ハノイの塔の解法プログラムを作成するためには、円盤を他の塔に移動させる処理が必要になります。
ハノイの塔ではルール上、円盤は積み重なっているものの一番上のものを移動する必要があります。そしてそれを他の塔の円盤の一番上に積み重ねます。
イメージとしてはスタックの POP と PUSH ですね。一番上のデータを取り出す、一番上にデータを追加する、というところはまさに同じ処理になります。
スタックについて知りたい方は下のページで解説していますのでこちらを参考にしてください。
【C言語/データ構造】スタックとキューの配列での実装方法
このページで紹介するプログラムでは円盤を移動する関数を move 関数として定義しています。第一引数に塔の状態を表すデータへのポインタ、第二引数に移動元の塔の行番号、第三引数に移動先の塔の行番号を指定することができ、実行することで第一引数の塔の状態を表すデータの移動元の行の円盤が移動先の行に移動します。つまり第一引数で指定したデータの中身が変わります。
ハノイの塔を解く関数
ハノイの塔の解法を行う関数は下記をそのまま実装すれば良いです。
- dst を work を置き換えて高さ N -1 のハノイの塔を解く
- src から dst へ移動
- src を work を置き換えて高さ N -1 のハノイの塔を解く
このページで紹介するソースコードでは、ハノイの塔を解く関数名を hanoi_func とし、引数としては「塔の状態を表すデータ（へのポインタ）」「塔の高さ」「src とする行番号」「dst とする行番号」「work とする行番号」を指定できるようにしています。
ですので、上記の３つの処理は下記のように記述することができます。
hanoi_func(tower, height - 1, src, work, dst);
move(tower, src, dst);
hanoi_func(tower, height - 1, work, src, dst);tower は塔の状態で解説した３つの塔の状態を表すデータへのポインタで、move は円盤の移動で解説した円盤を移動する関数になります。
src, dst, work はそれぞれ 0, 1, 2 に enum により名前をつけたものです。
height を 1 減らし、src や work, dst を入れ替えて hanoi_func を実行することで高さを１減らしたハノイの塔を解くことができます。
ハノイの塔の解法プログラム
最後にハノイの塔の解法プログラムの全体を載せておきます。
#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 の定義を変更すればいろんな高さのハノイの塔を解くことが可能です。塔の状態がどんどん変わっていく様子が面白いと思いますので、是非試して見てください。
スポンサーリンク
まとめ
今回はハノイの塔の解き方と、ハノイの塔を解くプログラムについて解説しました。再帰処理を使うと一見簡単そうに見えるソースコードで複雑な処理ができることを理解していただけたのではないかと思います。
