AOJ 1268 Cubic Eight-Puzzle

問題

6面が、赤、白、青に塗られた立方体が8つ並んだパズルがある。
このパズルの初期局面および、目的の局面が与えられたとき、
目的の局面に至るための手数の最小値を求めよ。


30手以内に目的の局面に至れない場合は-1を出力せよ。

方針

立方体の状態は6通りある。


反復深化深さ優先で探索する。
直前の状態に戻る手を調べないように、直前の方向を再帰に組み込む。
終了局面と異なる色の立方体の数から、制限手数で終了状態にどうやっても至れないものを枝刈りする。
上の二つの工夫をすればサンプルが大体一瞬で終わる。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int x, y, lim;
char f[3][3];
int dice[3][3][3], goal[3][3];

bool rec(int y, int x, int turn, int pre){
	int diff = 0;
	rep(i, 3) rep(j, 3) if(dice[i][j][0] != goal[i][j]) diff++;
	
	if(diff == 0) return 1;
	
	if(turn + diff - 1 <= lim) rep(d, 4){
		if((d + 2) % 4 == pre) continue;
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= 3 || nx >= 3) continue;
		rep(k, 3) swap(dice[y][x][k], dice[ny][nx][k]);
		swap(dice[y][x][0], dice[y][x][d % 2 ? 2 : 1]);
		if(rec(ny, nx, turn + 1, d)) return 1;
		swap(dice[y][x][0], dice[y][x][d % 2 ? 2 : 1]);
		rep(k, 3) swap(dice[y][x][k], dice[ny][nx][k]);
	}
	return 0;
}
bool ok(int m){
	lim = m;
	rep(i, 3) rep(j, 3){
		if(i == y && j == x) dice[i][j][0] = -1;
		else rep(k, 3) dice[i][j][k] = k;
	}
	return rec(y, x, 0, 100);
}
int main()
{
	while(cin >> x >> y, x){
		x--; y--;
		rep(i, 3) rep(j, 3){
			cin >> f[i][j];
			if(f[i][j] == 'W') goal[i][j] = 0;
			else if(f[i][j] == 'R') goal[i][j] = 1;
			else if(f[i][j] == 'B') goal[i][j] = 2;
			else goal[i][j] = -1;
		}
		
		int lo = -1, hi = 31, mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			if(ok(mid)) hi = mid;
			else lo = mid;
		}
		cout << (hi == 31 ? -1 : hi) << endl;
	}
	
	return 0;
}