这是一个比直接深搜要发杂点的题，自己刚开始做的时候，思路并不是很清晰，查找了一些相关解答后，顺利弄懂，这里的代码并非我写的，是csdn上一个朋友写的，不错，我只是稍微添加注释。
可以注意的是47到51行，55,56行。
1 #include <iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 #define maxnum 26 6 typedef struct{ 7 int l,r,u,d; 8 }data; 9 data squares[maxnum];//squares是输入的各种方块的类型数组，最多有25种类型 10 int squaresnum[maxnum],fillsquares[maxnum],testnum=0,line,all;//squaresnum是对应每一种类型方块的数量 11 //fillsquares是每一个位置的数组，指明应该放哪一种类型的方块 12 //line是几行几列，all是总共有的方块类型的数目 13 bool Judge(data Temp,data Compare){ 14 if(Temp.d==Compare.d && Temp.l==Compare.l 15 && Temp.r==Compare.r && Temp.u==Compare.u) 16 return true; 17 return false; 18 } 19 void Input(){ 20 21 all=0; 22 memset(squaresnum,maxnum,0); 23 for(int i=0,j ;i<line*line;i++){ 24 data Temp; 25 cin>>Temp.u>>Temp.r>>Temp.d>>Temp.l; 26 for(j=0;j<all;j++){ //判断方块类型是否已经存在，存在可不添加，数量加1 27 if( Judge(Temp,squares[j]) ){ 28 squaresnum[j]++; 29 break; //跳出循环 30 } 31 } 32 if(j==all) //如果不存在，则添加 33 squares[all]=Temp,squaresnum[all++]=1; 34 } 35 } 36 bool solve(int locate){ //找出第locate位置应该放那种类型的方块，和深搜差不多 37 38 if(locate==line*line) 39 return true; 40 41 int x=locate/line,y=locate%line,i; 42 43 for(i=0;i<all;i++){ 44 45 if(squaresnum[i]==0) 46 continue; 47 if(x>0 && squares[fillsquares[locate-line]].d!=squares[i].u ) 48 //它不是第一行并且上一个方块的下面与它的上面不相等 49 continue; //继续下一次判断 50 if(y>0 && squares[fillsquares[locate-1]].r!=squares[i].l) 51 //它不是第一列并且左边的方块的右边与它的左面不相等 52 continue; 53 fillsquares[locate]=i; // locate位置可以放第i种方块 54 squaresnum[i]--; //第i种方块减少一个 55 if(solve(locate+1)) return true;//这个return true还是很重要的 56 squaresnum[i]++;//如果下一个不合适了，得回溯一个方块 57 } 58 return false; 59 } 60 int main(){ 61 62 while(cin>>line && line ){ 63 64 if(testnum) 65 cout<<endl; 66 Input(); 67 cout<<"Game "<<++testnum<<": "; 68 puts(solve(0)?"Possible":"Impossible"); 69 } 70 return 0; 71 }