poj2676 Sudoku

题意：
数独游戏。
思路：
深搜。
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int n;
 5 int now[9][9], row[9][10], col[9][10], block[3][3][10];
 6 bool flag = false;
 7 
 8 bool check(int x, int y, int i)
 9 {
10     if (!row[x][i] && !col[y][i] && !block[x / 3][y / 3][i])
11     {
12         row[x][i] = col[y][i] = block[x / 3][y / 3][i] = 1;
13         return true;
14     }
15     return false;
16 }
17 
18 void back_trace(int x, int y, int i)
19 {
20     now[x][y] = row[x][i] = col[y][i] = block[x / 3][y / 3][i] = 0;
21 }
22 
23 void dfs(int x, int y)
24 {
25     if (flag)
26         return;
27     if (x == 9)
28     {
29         for (int i = 0; i < 9; i++)
30         {
31             for (int j = 0; j < 9; j++)
32             {
33                 cout << now[i][j];
34             }
35             puts("");
36         }
37         flag = true;
38         return;
39     }
40     int nx = (y == 8 ? x + 1 : x);
41     int ny = (y == 8 ? 0 : y + 1);
42     if (now[x][y])
43         dfs(nx, ny);
44     else
45     {
46         for (int i = 1; i <= 9; i++)
47         {
48             if (check(x, y, i))
49             {
50                 now[x][y] = i;
51                 dfs(nx, ny);
52                 back_trace(x, y, i);
53             }
54         }
55     }
56 }
57 int main()
58 {
59     cin >> n;
60     char tmp;
61     while (n--)
62     {
63         flag = false;
64         for (int i = 0; i < 9; i++)
65         {
66             for (int j = 1; j <= 9; j++)
67             {
68                 row[i][j] = col[i][j] = 0;
69             }
70         }
71         for (int i = 0; i < 3; i++)
72         {
73             for (int j = 0; j < 3; j++)
74             {
75                 for (int k = 1; k <= 9; k++)
76                     block[i][j][k] = 0;
77             }
78         }
79         for (int i = 0; i < 9; i++)
80         {
81             for (int j = 0; j < 9; j++)
82             {
83                 cin >> tmp;
84                 now[i][j] = tmp - '0';
85                 if (now[i][j])
86                 {
87                     row[i][now[i][j]] = 1;
88                     col[j][now[i][j]] = 1;
89                     block[i / 3][j / 3][now[i][j]] = 1;
90                 }
91             }
92         }
93         dfs(0, 0);
94     }
95     return 0;
96 }