9x9的格子中可以划分为9个3x3的小宫，对每一个格子可以尝试放置1～9个数，在放置前要判断是否冲突(conflict()),如果不冲突，就继续放置下一个格子，如果按照当前的放法无法得到正确的解，那么在回溯到当前位置后，要把当前位置重新置为0以便进行下一轮的搜索，因为只有当前值为0才能放置新值。 1 #include <iostream>
2 #include <string>
3 #include <stdio.h>
4 #include <string.h>
5 using namespace std;
6
7 const int SIZE = 9;
8 int grid[SIZE][SIZE];
9 char input[SIZE][SIZE+1];
10
11
12 bool conflict(int i, int j, int val) {
13 for (int k = 0; k < SIZE; ++k) {
14 if (grid[k][j] == val && k != i)//check the j colum
15 return true;
16 if (grid[i][k] == val && k != j)//check the i row
17 return true;
18 }
19 //caluate the first position of the 3x3 area
20 int row_s = i, col_s = j;
21 row_s /= 3;
22 col_s /= 3;
23 row_s *= 3;
24 col_s *= 3;
25
26 //check in 3x3 area
27 int r, c;
28 for (r = row_s; r < row_s + 3; ++r)
29 for (c = col_s; c < col_s + 3; ++c)
30 if (grid[r][c] == val && !(r == i && c == j))
31 return true;
32 return false;
33 }
34
35 void print(void);
36
37 bool dfs(int m) {
38 if (m == -1)
39 return true;
40
41 int i, j;
42 i = m / 9;
43 j = m % 9;
44 if (grid[i][j] == 0) {
45 for (int val = 1; val <= 9; ++val) {
46 if (!conflict(i, j, val)) {
47 grid[i][j] = val;
48 if (dfs(m-1) == true)
49 return true;
50 else grid[i][j] = 0;//!!!! add
51 }
52 }
53 return false; //we cannot find valid solution
54 } else {
55 if (dfs(m-1) == true)
56 return true;
57 return false; //we cannot find valid solution
58 }
59 }
60
61 void print(void) {
62 int i, j;
63
64 for (i = 0; i < SIZE; ++i) {
65 for (j = 0; j < SIZE; ++j)
66 cout << grid[i][j];
67 cout << endl;
68 }
69 }
70
71 int main(void)
72 {
73 int n, i, j;
74 int row_s, col_s;
75
76 scanf("%d", &n);
77 while (n--) {
78 for (i = 0; i < SIZE; ++i)
79 scanf("%s", input[i]);
80 for (i = 0; i < SIZE; ++i)
81 for (j = 0; j < SIZE; ++j)
82 grid[i][j] = input[i][j] - '0';
83
84 if (dfs(80) == true) {
85 cout << "success." << endl;
86 print();
87 } else {
88 cout << "failed." << endl;
89 print();
90 }
91 }
92 return 0;
93 }
94
95 /*
96
97 804009013
98 020360500
99 003400060
100 001047608
101 008010300
102 607800100
103 040003700
104 002074080
105 780600401
106
107 */
posted on 2012-09-14 10:48
lixiucheng 阅读(577)
评论(0) 编辑 收藏 引用