每行 每列 每个小九宫格里 某个数字是否存在 记录下来
#include #include #include #include #include #include #include #include #include using namespace std; int r[10][10],c[10][10],s[10][10],ma[10][10],zero; int dfs(int x,int y) { int i,flag,k; if(zero==0) return 1; if(x==10) return 0; if(ma[x][y]) { if(y==9) flag=dfs(x+1,1); else flag=dfs(x,y+1); if(flag) return 1; else return 0; } else { for(i=1;i<=9;i++) { k=3*((x-1)/3)+(y-1)/3+1; if(!r[x][i]&&!c[y][i]&&!s[k][i]) { r[x][i]=1; c[y][i]=1; s[k][i]=1; ma[x][y]=i; zero--; if(y==9) flag=dfs(x+1,1); else flag=dfs(x,y+1); if(flag) return 1; else { r[x][i]=0; c[y][i]=0; s[k][i]=0; ma[x][y]=0; zero++; } } } } return 0; } int main() { int i,j,t,a; scanf("%d",&t); getchar(); while(t--) { memset(r,0,sizeof r); memset(c,0,sizeof c); memset(s,0,sizeof s); zero=0; for(i=1;i<=9;i++) { for(j=1;j<=9;j++) { a=getchar()-'0'; ma[i][j]=a; if(a==0) zero++; else { r[i][a]=1; c[j][a]=1; s[3*((i-1)/3)+(j-1)/3+1][a]=1; } } getchar(); } dfs(1,1); for(i=1;i<=9;i++) { for(j=1;j<=9;j++) printf("%d",ma[i][j]); putchar('\n'); } } return 0; }