1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4  5 const int N = 9; 6 const int Group[9][9] = { 7     0, 0, 0, 1, 1, 1, 2, 2, 2, 8     0, 0, 0, 1, 1, 1, 2, 2, 2, 9     0, 0, 0, 1, 1, 1, 2, 2, 2,10     3, 3, 3, 4, 4, 4, 5, 5, 5,11     3, 3, 3, 4, 4, 4, 5, 5, 5,12     3, 3, 3, 4, 4, 4, 5, 5, 5,13     6, 6, 6, 7, 7, 7, 8, 8, 8,14     6, 6, 6, 7, 7, 7, 8, 8, 8,15     6, 6, 6, 7, 7, 7, 8, 8, 816 };17 18 int a[N][N],Line[N][N],Column[N][N],group[N][N]; 19 20 int print() {21     for(int i=0; i<N; i++) {22         for(int j=0; j<N; j++)23             cout<<a[i][j]+1<<" ";24             cout<<endl;25     }26 }27 28 void dfs(int x,int y) {29     if(x == N) {30         print();31         return ;32     }33     int nxt_x = x,nxt_y = y + 1;34     if(nxt_y == N) nxt_x = x + 1,nxt_y = 0; 35     36     if(a[x][y] >= 0) dfs(nxt_x,nxt_y);37     else {38         for(int i=0; i<N; i++) {39             if(!Line[x][i] && !Column[y][i] && !group[Group[x][y]][i]) {40                 Line[x][i] = Column[y][i] = group[Group[x][y]][i] = 1;41                 42                 a[x][y] = i;43                 dfs(nxt_x,nxt_y);44                 a[x][y] = -1;45                 46                 Line[x][i] = Column[y][i] = group[Group[x][y]][i] = 0;47             }48         }49     }50 }51 52 int main() {53     for(int i=0; i<N; i++)54         for(int j=0; j<N; j++)55             cin>>a[i][j], a[i][j]--;56     for(int i=0; i<N; i++)57         for(int j=0; j<N; j++)58             if(a[i][j] >= 0) {59                 Line[i][a[i][j]] = 1,60                 Column[j][a[i][j]] = 1,61                 group[Group[i][j]][a[i][j]] = 1;62             }63     dfs(0,0);64     return 0;65 }