题意：完成9*9的数独。
思路：直接DFS即可，判断该数是否在该行、该列、该九格中出现过。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <string> #include <math.h> #include <map> using namespace std; int d[10][10];//存储整个矩阵 int p[100][2];//存储需要填的点 int k;//需要填的点的个数 bool x[10][10],y[10][10],z[10][10];//标记数组 bool dfs(int v) { if(v==k) return true; for(int i=1;i<10;i++) { if(!x[p[v][0]][i] && !y[p[v][1]][i] && !z[p[v][0]/3*3+p[v][1]/3][i]) { d[p[v][0]][p[v][1]]=i; x[p[v][0]][i] = true; y[p[v][1]][i] = true; z[p[v][0]/3*3+p[v][1]/3][i]=true; if(dfs(v+1)) return true; d[p[v][0]][p[v][1]]=0; x[p[v][0]][i] = false; y[p[v][1]][i] = false; z[p[v][0]/3*3+p[v][1]/3][i]=false; } } return false; } int main() { int T; scanf("%d",&T); while(T--) { char s[10]; memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(z,0,sizeof(z)); k=0; for(int i=0;i<9;i++) { scanf(" %s",s); for(int j=0;j<9;j++) { d[i][j]=s[j]-'0'; if(d[i][j]==0) { p[k][0]=i; p[k++][1]=j; } else { x[i][d[i][j]]=true; y[j][d[i][j]]=true; z[i/3*3+j/3][d[i][j]]=true; } } } dfs(0); for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { printf("%d",d[i][j]); } printf(" "); } } return 0; }