问题描述:
数独问题
解题要点:
回溯时要恢复回溯之前的所有状态,一开始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