1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 bool row_f[9][10];//row_f[i][j]=1表示第i行已经放了数字j 8 bool col_f[9][10]; 9 bool block_f[9][10];10 int g[9][9];11 struct blank{12     int i, j;13     blank(int i, int j):i(i),j(j) {}14 };15 vector<blank> bk;16 int get_blockid(int i, int j){17     i /= 3;18     j /= 3;19     return i * 3 + j;20 }21 bool ok(int i, int j, int x){22     return !row_f[i][x] && !col_f[j][x] && !block_f[get_blockid(i, j)][x];23 }24 void setnum(int i, int j, int x, int f){25     row_f[i][x] = f;26     col_f[j][x] = f;27     block_f[get_blockid(i, j)][x] = f;28 }29 bool dfs(int n){//处理前n个空白格30     if(n < 0) return true;31     int r = bk[n].i;32     int c = bk[n].j;33     for(int x = 1; x <= 9; ++x){34         if(ok(r, c, x)){35             setnum(r, c, x, 1);36             g[r][c] = x;37             if(dfs(n - 1)) return true;38             setnum(r , c, x, 0);39         }40     }41     return false;42 }43 int main(){44     int t, i, j;45     char c;46     scanf("%d", &t);47     while(t--){48         bk.clear();49         memset(row_f, 0, sizeof(row_f));50         memset(col_f, 0, sizeof(col_f));51         memset(block_f, 0, sizeof(block_f));52         for(i = 0; i < 9; ++i){53             for(j = 0 ;j < 9; ++j){54                 cin >> c;55                 g[i][j] = c - ‘0‘;56                 if(!g[i][j])57                     bk.push_back(blank(i, j));58                 else59                     setnum(i, j, g[i][j], 1);60             }61         }62         if(dfs(bk.size()-1)){63             for(i = 0; i < 9; ++i){64                 for(j = 0; j < 9 ; ++j)65                     printf("%c", g[i][j] + ‘0‘);66                 printf("\n");67             }68         }69     }70     return 0;71 }