数独问题
采用跳舞链方法会得到比较快的速度
用跳舞链解决的方法主要是将问题的模型转换成01覆盖模型,然后模板之
首先要了解它的限制条件:
(1) 每一格只能填一个数字
(2) 每一列的数字是不同的
(3) 每一行的数字是不同的
(4) 每一个九宫格的数字是不同的
那么我们可以构造出一组状态:
行状态(i,j,k):表示第i行第j列填第k个数
列状态(i,j,k):表示第k个限制的子状态为(i,j),子状态根据限制而定
所以对于N层数独来说,行有N*N*N,列有4*N*N
然后对于给出的数独,如果改格子没有数字就枚举每个可能出现的数字插入,有数字就插入现成的,然后用跳舞链一下,就出结果了
代码:
1
#include <stdio.h>
2
#include <string.h>
3![](/Images/OutliningIndicators/None.gif)
4
const int N = 9;
5![](/Images/OutliningIndicators/None.gif)
6
const int MAX_WIDTH = 4*N*N+10;
7
const int MAX_HEIGHT =N*N*N+10 ;
8![](/Images/OutliningIndicators/None.gif)
9
struct DancingLinkNode
10![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
11
int row;
12
int col;
13
DancingLinkNode* pR,*pL,*pU,*pD;
14
};
15
DancingLinkNode memPool[MAX_WIDTH*MAX_HEIGHT];
16![](/Images/OutliningIndicators/None.gif)
17
class DancingLink
18![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
19
private:
20
DancingLinkNode head;
21
DancingLinkNode rows[MAX_HEIGHT];
22
DancingLinkNode columns[MAX_WIDTH];
23
int size[MAX_WIDTH];
24
int nodeUseNum;//use to the memory pool
25
public:
26
int len;
27
int ans[MAX_HEIGHT];
28
DancingLink()
29![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
30
}
31
void init(int _r,int _c)
32![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
33
nodeUseNum = 0;
34
head.row = _r;
35
head.col = _c;
36
head.pD = head.pL = head.pR = head.pU = &head;
37![](/Images/OutliningIndicators/InBlock.gif)
38
for(int i = 0; i < _c; ++i)
39![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
columns[i].row = _r;
41
columns[i].col = i;
42
columns[i].pL = &head;
43
columns[i].pR = head.pR;
44
columns[i].pL->pR = &columns[i];
45
columns[i].pR->pL = &columns[i];
46
columns[i].pU = columns[i].pD = &columns[i];
47
size[i] = 0;
48
}
49![](/Images/OutliningIndicators/InBlock.gif)
50
for(int i = _r - 1; i >= 0; --i)
51![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
52
rows[i].col = _c;
53
rows[i].row = i;
54
rows[i].pU = &head;
55
rows[i].pD = head.pD;
56
rows[i].pU->pD = &rows[i];
57
rows[i].pD->pU = &rows[i];
58
rows[i].pL = rows[i].pR = &rows[i];
59
}
60
memset(ans,0,sizeof(ans));
61
len = 0;
62
}
63![](/Images/OutliningIndicators/InBlock.gif)
64
void addNode(int _r,int _c)
65![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
66
DancingLinkNode* newNode = &memPool[nodeUseNum++];
67
newNode->col = _c;
68
newNode->row = _r;
69
70
newNode->pR = &rows[_r];
71
newNode->pL = rows[_r].pL;
72
newNode->pL->pR = newNode;
73
newNode->pR->pL = newNode;
74![](/Images/OutliningIndicators/InBlock.gif)
75
newNode->pD = &columns[_c];
76
newNode->pU = columns[_c].pU;
77
newNode->pU->pD = newNode;
78
newNode->pD->pU = newNode;
79![](/Images/OutliningIndicators/InBlock.gif)
80
++size[_c];
81![](/Images/OutliningIndicators/InBlock.gif)
82
}
83
void removeByLR(DancingLinkNode* _node)
84![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
85
_node->pL->pR = _node->pR;
86
_node->pR->pL = _node->pL;
87
}
88
void removeByUD(DancingLinkNode* _node)
89![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
90
_node->pD->pU = _node->pU;
91
_node->pU->pD = _node->pD;
92
}
93
94
void resumeByLR(DancingLinkNode* _node)
95![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
96
_node->pL->pR = _node;
97
_node->pR->pL = _node;
98
}
99![](/Images/OutliningIndicators/InBlock.gif)
100
void resumeByUD(DancingLinkNode* _node)
101![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
102
_node->pD->pU = _node;
103
_node->pU->pD = _node;
104
}
105![](/Images/OutliningIndicators/InBlock.gif)
106
void cover(int _c)
107![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
108
if(_c >= 0 && _c < head.col)
109![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
110
removeByLR(&columns[_c]);
111
for(DancingLinkNode* pCol = columns[_c].pD; pCol != &columns[_c]; pCol = pCol->pD)
112![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
113
if(pCol->col == head.col)
114![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
115
continue;
116
}
117
for(DancingLinkNode* pRow = pCol->pR; pRow != pCol; pRow = pRow->pR)
118![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
119
if(pRow->col == head.col)
120![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
121
continue;
122
}
123
--size[pRow->col];
124
removeByUD(pRow);
125
}
126
removeByLR(pCol);
127
}
128
}
129
}
130![](/Images/OutliningIndicators/InBlock.gif)
131
void resume(int _c)
132![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
133
if(_c >= 0 && _c < head.col)
134![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
135
for(DancingLinkNode* pCol = columns[_c].pU; pCol != &columns[_c]; pCol = pCol->pU)
136![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
137
if(pCol->col == head.col)
138![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
139
continue;
140
}
141
resumeByLR(pCol);
142
for(DancingLinkNode* pRow = pCol->pL; pRow != pCol; pRow = pRow->pL)
143![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
144
if(pRow->col == head.col)
145![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
146
continue;
147
}
148
++size[pRow->col];
149
resumeByUD(pRow);
150
}
151
}
152
resumeByLR(&columns[_c]);
153
}
154
}
155![](/Images/OutliningIndicators/InBlock.gif)
156![](/Images/OutliningIndicators/InBlock.gif)
157
bool dfs(int _k)
158![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
159
if(head.pL == &head)
160![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
161
len = _k;
162
return true;
163
}
164
//选择列(最小元素优先)
165
int minV = (1 << 30);
166
int minVcol = -1;
167
for(DancingLinkNode* pNode = head.pL; pNode != &head; pNode = pNode->pL)
168![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
169
if(size[pNode->col] < minV)
170![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
171
minV = size[pNode->col];
172
minVcol = pNode->col;
173
}
174
}
175
cover(minVcol);
176
for(DancingLinkNode* pNode = columns[minVcol].pD; pNode != &columns[minVcol]; pNode = pNode->pD)
177![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
178
ans[_k] = pNode->row;
179
pNode->pL->pR = pNode;
180
for(DancingLinkNode* pNode2 = pNode->pR; pNode2 != pNode; pNode2 = pNode2->pR)
181![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
182
cover(pNode2->col);
183
}
184
if(dfs(_k+1))
185![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
186
return true;
187
}
188
pNode->pR->pL = pNode;
189
for(DancingLinkNode* pNode2 = pNode->pL; pNode2 != pNode; pNode2 = pNode2->pL)
190![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
191
resume(pNode2->col);
192
}
193
pNode->pL->pR = pNode->pR;
194
}
195
resume(minVcol);
196
return false;
197
}
198![](/Images/OutliningIndicators/InBlock.gif)
199
void Print()
200![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
201
for(DancingLinkNode* pRow = head.pD; pRow != &head; pRow = pRow->pD)
202![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
203
if(pRow->row == head.row)
204![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
205
continue;
206
}
207
for(DancingLinkNode* pCol = pRow->pR; pCol != pRow; pCol = pCol->pR)
208![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
209
if(pCol->col == head.col)
210
continue;
211
printf("(%d %d),",pCol->row,pCol->col);
212
}
213
printf("\n");
214
}
215
}
216
};
217
DancingLink DLX;
218
char str[320];
219![](/Images/OutliningIndicators/None.gif)
220
void Insert(int _r,int _c,int _k)
221![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
222
int t = N*_r + _c;
223
int R = N*N*_k + t ;
224
int C = t ;
225
int B = ((int)(_r/3))*3 + _c/3;
226![](/Images/OutliningIndicators/InBlock.gif)
227
DLX.addNode(R,C);
228
C = N*N + N*_r + _k;
229
DLX.addNode(R,C);
230
C = 2*N*N + N*_c + _k;
231
DLX.addNode(R,C);
232
C = 3*N*N + N*B + _k;
233
DLX.addNode(R,C);
234
}
235![](/Images/OutliningIndicators/None.gif)
236
void PrintAns()
237![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
238
int reAns[N][N];
239
for(int i = 0; i < DLX.len; ++i)
240![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
241
int k = DLX.ans[i] / (N*N);
242
int r = (DLX.ans[i] - k*N*N)/N;
243
int c = DLX.ans[i] - k*N*N - r*N;
244
reAns[r][c] = k+1;
245
}
246
for(int i = 0; i < N; ++i)
247![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
248
for(int j = 0; j < N; ++j)
249![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
250
printf("%d",reAns[i][j]);
251
}
252
}
253
printf("\n");
254
}
255![](/Images/OutliningIndicators/None.gif)
256
void Test()
257![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
258
DLX.init(N*N*N,4*N*N);
259
for(int i = 0; i < N; ++i)
260![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
261
for(int j = 0; j < N; ++j)
262![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
263
if(str[i*N+j] == '.')
264![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
265
for(int k = 0; k < N; ++k)
266![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
267
Insert(i,j,k);
268
}
269
}
270
else
271![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
272
Insert(i,j,str[i*N+j]-'1');
273
}
274
}
275
}
276
if(DLX.dfs(0))
277![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
278
PrintAns();
279
}
280
}
281![](/Images/OutliningIndicators/None.gif)
282
int main()
283![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
284
while(gets(str))
285![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
286
if(strcmp(str,"end") == 0)
287
break;
288
Test();
289
}
290
return 0;
291
} 同理,3076如法炮制
posted on 2012-03-12 19:37
bennycen 阅读(2034)
评论(3) 编辑 收藏 引用 所属分类:
算法题解