问题描述：
数独问题
解题要点:
回溯时要恢复回溯之前的所有状态，一开始s数组回溯时忘了清零所以结果很奇怪
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117 |
#include<iostream>#include<cstdio>#include<algorithm>#include<string.h>#include<string>#include<cstring>using
namespace std;const
int maxn = 10;char
input[maxn][maxn];int
s[maxn][maxn];int
cubicrecord[maxn][maxn];int
linerecord[maxn][maxn];int
columnrecord[maxn][maxn];bool
success = false;void
dfs(int
id);int
main(){ //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int
t,i,j,part; scanf("%d",&t); while(t--) { success = false; memset(cubicrecord,0,sizeof(cubicrecord)); memset(linerecord,0,sizeof(linerecord)); memset(columnrecord,0,sizeof(columnrecord)); memset(s,0,sizeof(s)); memset(input,0,sizeof(input)); for(i = 1; i < maxn;++i) { scanf("%s",input[i]); for(j = 1; j < maxn; ++j) { s[i][j] = input[i][j-1] - ‘0‘; //scanf("%d",s[i]+j); part = ((i-1)/3)*3+((j-1)/3+1); //p[i][j] = part; cubicrecord[part][s[i][j]] = 1; linerecord[i][s[i][j]]=1; columnrecord[j][s[i][j]]=1; } } /*for(i = 1; i < maxn; ++i){ for(j = 1; j < maxn;++j){ printf("%d",p[i][j]); } printf("\n"); } return 0;*/ dfs(1); for(i = 1; i < maxn; ++i){ for(j = 1; j < maxn; ++j){ printf("%d",s[i][j]); } printf("\n"); } } return
0;}void
dfs(int
id){ if(success) return; int
x = (id - 1) / 9 + 1; int
y = (id - 1) % 9 + 1; int
part = ((x-1)/3)*3+((y-1)/3+1); if(id == 81) { if(s[x][y]) { success = true; return; } for(int
i = 1; i < maxn; ++i) { if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i])) { s[9][9] = i; success = true; break; } } return; } if(s[x][y]) //这个格子已经填完了 { dfs(id+1); if(success) return; } else { for(int
i = 1; i < maxn; ++i) { if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i])) { s[x][y] = i; linerecord[x][i] = 1; columnrecord[y][i] = 1; cubicrecord[part][i] = 1; dfs(id+1); if(success) break; linerecord[x][i] = 0; columnrecord[y][i] = 0; cubicrecord[part][i] = 0; s[x][y] = 0; } } if(success) return; }} |
原文：http://www.cnblogs.com/warmfrog/p/3648456.html