Problem 1116 : Jigsaw Puzzles for Computers

問題概要

以下のようなコンピュータ用のジグソーパズルがある。
各ピースは正方形で、それぞれの辺にはアルファベット1文字が書かれている。
接する辺のアルファベットの大文字小文字が異なり、同じ文字であるようなピースが隣接できる。

ピースは9つあり、これを3x3の正方形に上の条件を満たして並べる場合の数を求めよ。

解法

深さ優先探索により解を全部列挙する。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
int ans,sp[3][3];
char pc[9][5];
bool use[9];

void rec(int c)
{
	if(c==9)
	{
		ans++; return;
	}
	rep(i,9)if(!use[i])
	{
		sp[c/3][c%3]=i; use[i]=1;
		rep(rt,4)
		{
			rep(d,4)
			{
				int y=c/3+dy[d],x=c%3+dx[d];
				if(y<0||x<0||y>=3||x>=3||sp[y][x]<0)continue;
				char c1=pc[i][d],c2=pc[sp[y][x]][d^2];
				if(abs(c1-c2)!=abs('A'-'a'))goto FAIL;
			}
			rec(c+1);
			FAIL:
			rotate(pc[i],pc[i]+1,pc[i]+4);
		}
		sp[c/3][c%3]=-1; use[i]=0;
	}
}

int sol()
{
	rep(i,9)use[i]=0,sp[i/3][i%3]=-1; ans=0;
	rec(0);
	return ans;
}

int main()
{
	int n; scanf("%d",&n);
	rep(i,n)
	{
		rep(j,9)scanf("%s",pc[j]);
		printf("%d\n",sol());
	}
	return 0;
}