现在zoj暂时关了，实际上是在scuoj上做的。
看起来题目比较复杂，实际上主要需要思维的是如何恰当的剪枝及合适的DFS角度。
问题等价于将n*n个可能相同的方块放到一个n*n的表中，使满足题目要求的条件。由于放的时候是一个个放的，所以可以以此为切入点进行DFS，并且，只需要关注不同方块的种类，这样就可以极大的节约时间（从人做这件事的角度来看，相同的方块就像是相同的积木一样，人关注的只是相同的积木的形状以及个数。）
#include<cstdio>
#include<cstring>
using namespace std;
int a[][],kind[],n,kge,b[][],cnt=,m;//a记录不同种类方块各方向的数，kind记录每种种类的个数，kge记录种类数
int dfs(int p)
{
if(p==m)//dfs成功的话，就是进行到第n*n次（这时前0——n*n-1都已经放好）
return ;
else
{
for(int i=;i<kge;i++)
{
if(kind[i]==)
continue;
else
{
if(p%n!=)//p%n时左侧就没有方块
{
if(b[p-][]!=a[i][])
continue;
}
if(p>=n)//p<n时在最上一行，上面就没有方块
{
if(b[p-n][]!=a[i][])
continue;
}
kind[i]--;
for(int j=;j<;j++)
{
b[p][j]=a[i][j];
}
if(dfs(p+))//继续dfs下一个位置
{
return ;
}
kind[i]++;//如果这样并不行，恢复至之前的状态
}
}
return ;
}
}
int main()
{
while(scanf("%d",&n))
{
kge=;
if(n==)
break;
else
{
int up,left,right,down,i,j;
m=n*n;
for(i=;i<m;i++)
{
scanf("%d%d%d%d",&up,&right,&down,&left);
for(j=;j<kge;j++)
{
if(a[j][]==up&&a[j][]==right&&a[j][]==down&&a[j][]==left)
{
kind[j]++;
break;
}
}
if(j==kge)//整体是对有无与之前的方块相同的判断
{
a[kge][]=up;
a[kge][]=right;
a[kge][]=down;
a[kge][]=left;
kind[kge]=;
kge++;
}
}
if(cnt)
puts("");//注意空行
if(dfs())
printf("Game %d: Possible\n",++cnt);
else
printf("Game %d: Impossible\n",++cnt);
}
}
return ;
}