1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 bool v[10][10],row[10][10],col[10][10],used[4][4][10]; 5 int a[10][10]; 6 bool flag; 7 void dfs(int x,int y) 8 { 9     if (flag) return ;10     if (x>9)11     {12         for (int i=1;i<=9;i++)13         {14             for (int j=1;j<=9;j++) printf("%d",a[i][j]);15             printf("\n");16         }17         flag=true;18         return;19     }20 21     if (v[x][y]==1)22     {23         if (y==9) dfs(x+1,1);24         else dfs(x,y+1);25     }26     else27     {28         v[x][y]=1;29         for (int i=1;i<=9;i++)30             if (row[x][i]==0 && col[y][i]==0 && used[(x-1)/3+1][(y-1)/3+1][i]==0)31             {32                 a[x][y]=i;33                 row[x][i]=1;34                 col[y][i]=1;35                 used[(x-1)/3+1][(y-1)/3+1][i]=1;36                 if (y==9) dfs(x+1,1);else dfs(x,y+1);37                 a[x][y]=0;38                 row[x][i]=0;39                 col[y][i]=0;40                 used[(x-1)/3+1][(y-1)/3+1][i]=0;41             }42         v[x][y]=0;43     }44 }45 46 int main()47 {48     int n;49     scanf("%d",&n);50     for (int t=1;t<=n;t++)51     {52         memset(a,0,sizeof(a));53         memset(v,0,sizeof(v));54         memset(row,0,sizeof(row));55         memset(col,0,sizeof(col));56         memset(used,0,sizeof(used));57         for(int i=1;i<=9;i++)58         {59             char str[10];60             scanf("%s",str);61             for (int j=0;j<9;j++)62             {63                 a[i][j+1]=str[j]-‘0‘;64                 if (a[i][j+1]!=0)65                 {66                     v[i][j+1]=1;67                     int x=a[i][j+1];68                     row[i][x]=1;69                     col[j+1][x]=1;70                     used[(i-1)/3+1][(j+1-1)/3+1][x]=1;71                 }72             }73         }74 /*75         for (int i=1;i<=9;i++)76         {77             for (int j=1;j<=9;j++) printf("%d ",row[i][j]);78             printf("\n");79         }80 */81         flag=false;82         dfs(1,1);83     }84     return 0;85 }