数独。。。
用DFS做。
刚开始想用一个列表表示某一列，某一行出现了哪些数，后来看到别人用二维数组挺方便的。
跟普通DFS差不多，不过要判断是否换行，能 深搜 到最后一个点 表示 DFS做完了。
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int map[12][12]; bool row[12][12]; bool col[12][12]; bool g[12][12]; bool DFS(int x,int y) { if(x==10) return true; bool flag=false; if(map[x][y]) { if(y==9) flag=DFS(x+1,1); else flag=DFS(x,y+1); if(flag) return true; else return false; } else { int k=3*((x-1)/3)+(y-1)/3+1; for(int i=1;i<=9;i++) if(!row[x][i] && !col[y][i] && !g[k][i]) { map[x][y]=i; row[x][i]=true; col[y][i]=true; g[k][i]=true; if(y==9) flag=DFS(x+1,1); else flag=DFS(x,y+1); if(!flag) { map[x][y]=0; row[x][i]=false; col[y][i]=false; g[k][i]=false; } else return true; } } return false; } int main() { int T; char ch; scanf("%d",&T); while(T--) { memset(row,false,sizeof(row)); memset(col,false,sizeof(col)); memset(g,false,sizeof(g)); for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { cin>>ch; map[i][j]=ch-'0'; if(map[i][j]) { row[i][map[i][j]]=true; col[j][map[i][j]]=true; int k=3*((i-1)/3)+(j-1)/3+1; g[k][map[i][j]]=true; } } DFS(1,1); for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) printf("%d",map[i][j]); printf(" "); } } return 0; }