题目大意：给出一道数独题，判断该数独是否有解且有唯一解。
解题思路：
由前几题的难度得，此题的难度不会太过分，所以简单暴力就可以了，40ms用时一本满足。
简单地讲一下具体的实现，从左上开始从左到右从上到下一格一格枚举过去，枚举当前格子的数字时，判断一下这个数字能不能用就行了（判断是否在该行，该列，该区域出现过），全部填满时就找到了一个解，找到第二个解的时候停止搜索即可。
关于判断某个数字在当前区域是否用过，比较方便的方法是，事先算好p[i][j]，用来记录第i行第j格属于哪一列，哪一行，哪一区域，这样在写dfs时会方便很多。
代码：
/* 被注释掉的代码都是用来调试的，取消注释后可以用来查看程序运行过程以便调试。 */#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> using namespace std; #define FOR(i,a,b) for(int i=a;i<=b;i++) #define MST(a,b) memset(a,b,sizeof(a)) #define MAXL 10 int error;//用于发现不合理时终止程序 int g[MAXL][MAXL];//存放数组初始状态 int p1[MAXL][MAXL],p2[MAXL][MAXL],p3[MAXL][MAXL];//分别记录(i,j)所对应的行，列，区域 int b1[MAXL][MAXL],b2[MAXL][MAXL],b3[MAXL][MAXL];//记录编号为i的行，列，区域的数字使用情况 void init()//读入部分 {error=0;FOR(i,1,9)FOR(j,1,9)scanf("%d",&g[i][j]);MST(b1,0);MST(b2,0);MST(b3,0);FOR(i,1,9)FOR(j,1,9)if(g[i][j]){int p=p1[i][j],x=g[i][j];if(b1[p][x])error=1;b1[p][x]=1;p=p2[i][j];if(b2[p][x])error=1;b2[p][x]=1;p=p3[i][j];if(b3[p][x])error=1;b3[p][x]=1;} } int g2[MAXL][MAXL];//调试时用的数组，可无视 int tot;//记录解的个数 void dfs(int x,int y) {if(x==10)//dfs到第10行意味着已经全部填满 {tot++;if(tot>1)error=1;//若发现第二个解则终止程序/*FOR(i,1,9){FOR(j,1,9)printf("%d ",g2[i][j]+g[i][j]);printf("\n");}printf("\n");*/return;}int xt=x,yt=y+1;//计算下一个if(yt>9){xt++;yt=1;}if(g[x][y]){dfs(xt,yt);return;}//若该格已有数字则无需尝试，直接进入下一格int c1=p1[x][y],c2=p2[x][y],c3=p3[x][y];//记录当前格所在的行，列，区域的编号FOR(i,1,9)if(b1[c1][i]+b2[c2][i]+b3[c3][i]==0)//是否在当前行，列，区域都未使用 {b1[c1][i]=1;b2[c2][i]=1;b3[c3][i]=1;//g2[x][y]=i;dfs(xt,yt);//进入下一格继续尝试//g2[x][y]=0;if(error)return;b1[c1][i]=0;b2[c2][i]=0;b3[c3][i]=0;} } void work()//计算部分g2和输出error什么的请无视 {MST(g2,0);tot=0;dfs(1,1);//if(error)printf("error");if(tot==0 || error)printf("No\n");else printf("Yes\n"); } int main() {freopen("in.txt","r",stdin);//文件输入以便调试//freopen("out.txt","w",stdout);FOR(i,1,9)FOR(j,1,9)p1[i][j]=i;FOR(i,1,9)FOR(j,1,9)p2[i][j]=j;FOR(i,1,9)FOR(j,1,9)p3[i][j]=((i-1)/3)*3+((j-1)/3)+1;//预处理i,j所在区域/*FOR(i,1,9){FOR(j,1,9)printf("%d ",p3[i][j]);printf("\n");}*///上面的代码用来检查预处理时有无算错，下面开始是正片int nn;scanf("%d",&nn);FOR(ii,1,nn){init();if (error){printf("No\n");continue;}work();}}
