ドラクエVIIのバロックタワーのパズルを解く

Programming

※この記事にはドラクエVIIのネタバレがあります。ご注意ください。

最近はせっせとドラクエVIIをやっています。

今夜も帰宅してから遊んでいたところ、バロックタワー内部のパズルでハマってしまいました。

というわけで、( ﾟ∀ﾟ)o彡°DDD! DDD! （ドラクエ駆動開発）

問題

このように4つの像があります。

最初はバラバラの方向を向いている像を、一度に3つずつ動かして、4つを向き合わせるのがゴールです。

動かし方には、次の4パターンがあります。実行する順番や回数に、制限はありません。

（よくあるパズルですが、自分は大の苦手です。図を描いて5分くらい考えても解けません。得意な人は数秒で解けると聞きます。すごいですね）

回答

  • 入力: 4つの像の向き
  • 出力: ボタンの押すべき順番

と、しました。

public class Baroque {

	protected int STATUE_NUM = 4;
	protected int LIMIT = 8;
	protected int counter = 0;
	protected String result = "";

	protected int turn(int i) {
		if (i == STATUE_NUM - 1) {
			return 0;
		}
		return i + 1;
	}

	protected boolean isOK(final int[] data) {
		if (data[0] == 2 && data[1] == 3 && data[2] == 0 && data[3] == 1) {
			return true;
		}
		return false;
	}

	protected int[] getNextData(final int[] data, final int button) {
		int ex = turn(button);
		int[] result = new int[STATUE_NUM];
		for (int i = 0; i < STATUE_NUM; i++) {
			if (i == ex) {
				result[i] = data[i];
			} else {
				result[i] = turn(data[i]);
			}
		}
		return result;
	}

	protected boolean loop(int[] data) {
		int[] tmp = new int[STATUE_NUM];
		String _result = result;
		for (int i = 0; i < STATUE_NUM; i++) {
			result += String.valueOf(i);
			tmp = getNextData(data, i);
			if (isOK(tmp)) {
				return true;
			}
			if (counter < LIMIT) {
				counter++;
				boolean b = loop(tmp);
				if (b) {
					return true;
				}
				result = _result;
				counter--;
			}
			result = _result;
		}
		return false;
	}

	protected String solve(final String[] input) {
		int[] data = getData(input);
		loop(data);
		return result;
	}

	protected int[] getData(final String[] input) {
		if (input.length != STATUE_NUM) {
			throw new IllegalArgumentException(
					"上右下左の順で，4つの像の向きを入力してください．0（上），1（右），2（下），3（左）");
		}
		int[] result = new int[STATUE_NUM];
		for (int i = 0; i < STATUE_NUM; i++) {
			result[i] = Integer.valueOf(input[i]);
		}
		return result;
	}

	public static void main(String[] args) {
		Baroque b = new Baroque();
		String[] s = new String[] { "3", "2", "2", "3" };
		System.out.println(b.solve(s));
	}
}

配列の値は、こんな感じに。

  • 像の番号: 上=0, 右=1, 下=2, 左=3
  • 像の向き: 上=0, 右=1, 下=2, 左=3
  • ボタン: 像0と1の間=0, 像1と2の間=1, 像2と3の間=2, 像3と0の間=3

8階層くらいまでで答えが出ると想定して、それ以上の深さは探索しませんでした。答えが出ない時は、LIMITの値を増やせばよいでしょう。

（mainで与えている入力値は、初期値ではなく、アナログで散々試行錯誤した回答途中のものです。念のため）

ヤッター解けたよー。

ではでは。。。（ドラクエに戻ります）

（2013/2/22 追記） 皆さんの解法

見かけたら追加します。