FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

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

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

あうとらいん

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

要するに、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;
}