困難版ハノイの塔を解いてみた

「困難版ハノイの塔」とは、深夜の『コマ大なんとか』とかいう番組で取り上げられていた変形版ハノイの塔のこと。昨日の授業でこの問題の話が出てきたので、いっちょプログラムを作ってみた。

あうとらいん

この問題は有名な「ハノイの塔」というパズルをベースにしたものなのだが、その概要を言葉で伝えるのは大変なので、適当に図で説明してしまおう。

要するに、3つの軸にこんな感じで積み重なった円盤を

こんな感じに移動することができれば完成。ただし、以下のルールを守った上で、できる限り円盤の移動を少なくしなければならない。

1. 一度に動かせるのは1つの円盤のみ。
2. 円盤の上にそれより大きい円盤を乗せちゃダメ。

シンプルでありながら意外と頭を使う問題なので、まずは紙の上で解法を考えてみてくださいな。まだ普通のハノイの塔を解いたことがないという人は、先に通常版ハノイの塔を攻略しておきましょう。

＠C言語

再帰ってすばらしー。

#include <stdio.h>

int count;

// 普通のハノイの塔だけど、動かす枚数は2倍
int sub_hanoi(int n, char *start, char *goal, char *tmp)
{
	if (n == 0) return 0;
	sub_hanoi(n-1, start, tmp, goal);
	printf("%s -> %s\n", start, goal);
	printf("%s -> %s\n", start, goal);
	sub_hanoi(n-1, tmp, goal, start);
	count += 2;
	return 0;
}

// 困難版ハノイの塔のアルゴリズム
// 問題サイズ、移動元の軸A、移動元の軸B、移動先の軸、0
int hanoi(int n, char *start1, char *start2, char *goal, int type)
{
	if (n == 0) return 0;
	if (type == 0) {
		// 下から数えて奇数段
		hanoi(n-1, start1, start2, goal, 1);
		printf("%s -> %s\n", start1, goal);
		sub_hanoi(n-1, start2, start1, goal);
		printf("%s -> %s\n", start2, goal);
		sub_hanoi(n-1, start1, goal, start2);
		count += 2;
	} else {
		// 下から数えて偶数段
		hanoi(n-1, start1, start2, goal, 0);
		printf("%s -> %s\n", start1, start2);
		sub_hanoi(n-1, goal, start2, start1);
		count++;
	}
	return 0;
}

int main()
{
	hanoi(3, "左", "右", "中", 0);
	printf("手数 = %d\n", count);
	return 0;
}