POJ --- 2676 Sudoku

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int map[20][20], cnt[10];
 6 char str[10][10];
 7 bool Judge(int x, int y, int num){
 8     for(int i = 1;i <= 9;i ++){
 9         if(map[x][i] == num || map[i][y] == num)
10             return false;
11     }
12     int row = 1 + ((x - 1) / 3)*3;
13     int col = 1 + ((y - 1) / 3)*3;
14     for(int i = row;i < row + 3;i ++){
15         for(int j = col;j < col + 3;j ++)
16             if(map[i][j] == num) return false;
17     }
18     return true;
19 }
20 bool dfs(int x, int y){
21     if(y == 10){
22         y = 1;
23         x ++;
24         if(x == 10) return true;
25     }
26     while(map[x][y] != 0){
27         y ++;
28         if(y == 10){
29             y = 1;
30             x ++;
31         }
32         if(x == 10) return true;
33     }
34     for(int i = 1;i <= 9;i ++){
35         if(Judge(x, y, i)){
36             map[x][y] = i;
37             if(dfs(x, y+1)) return true;
38             map[x][y] = 0;
39         }
40     }
41     return false;
42 }
43 int main(){
44     int T;
45     //freopen("in.c", "r", stdin);
46     scanf("%d", &T);
47     while(T--){
48         memset(map, -1, sizeof(map));
49         for(int i = 0;i < 9;i ++){
50             scanf("%s", str[i]);
51         }
52         for(int i = 0;i < 9;i ++){
53             for(int j = 0;j < 9;j ++){
54                 map[i+1][j+1] =  str[i][j] - ‘0‘;
55             }
56         }
57         dfs(1, 1);
58         for(int i = 1;i <= 9;i ++){
59             for(int j = 1;j <= 9;j ++)
60                 printf("%d", map[i][j]);
61             printf("\n");
62         }
63     }
64     return 0;
65 }