數獨問題
采用跳舞鏈方法會得到比較快的速度
用跳舞鏈解決的方法主要是將問題的模型轉換成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
4const int N = 9;
5
6const int MAX_WIDTH = 4*N*N+10;
7const int MAX_HEIGHT =N*N*N+10 ;
8
9struct DancingLinkNode
10
{
11
int row;
12 int col;
13 DancingLinkNode* pR,*pL,*pU,*pD;
14
};
15DancingLinkNode memPool[MAX_WIDTH*MAX_HEIGHT];
16
17class DancingLink
18{
19private:
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
25public:
26 int len;
27 int ans[MAX_HEIGHT];
28 DancingLink()
29
{
30
}
31 void init(int _r,int _c)
32 {
33 nodeUseNum = 0;
34 head.row = _r;
35 head.col = _c;
36 head.pD = head.pL = head.pR = head.pU = &head;
37
38 for(int i = 0; i < _c; ++i)
39 {
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
50 for(int i = _r - 1; i >= 0; --i)
51 {
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
64 void addNode(int _r,int _c)
65 {
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
75 newNode->pD = &columns[_c];
76 newNode->pU = columns[_c].pU;
77 newNode->pU->pD = newNode;
78 newNode->pD->pU = newNode;
79
80 ++size[_c];
81
82 }
83 void removeByLR(DancingLinkNode* _node)
84 {
85 _node->pL->pR = _node->pR;
86 _node->pR->pL = _node->pL;
87 }
88 void removeByUD(DancingLinkNode* _node)
89 {
90 _node->pD->pU = _node->pU;
91 _node->pU->pD = _node->pD;
92 }
93
94 void resumeByLR(DancingLinkNode* _node)
95 {
96 _node->pL->pR = _node;
97 _node->pR->pL = _node;
98 }
99
100 void resumeByUD(DancingLinkNode* _node)
101 {
102 _node->pD->pU = _node;
103 _node->pU->pD = _node;
104 }
105
106 void cover(int _c)
107 {
108 if(_c >= 0 && _c < head.col)
109 {
110 removeByLR(&columns[_c]);
111 for(DancingLinkNode* pCol = columns[_c].pD; pCol != &columns[_c]; pCol = pCol->pD)
112 {
113 if(pCol->col == head.col)
114 {
115 continue;
116 }
117 for(DancingLinkNode* pRow = pCol->pR; pRow != pCol; pRow = pRow->pR)
118 {
119 if(pRow->col == head.col)
120 {
121 continue;
122 }
123 --size[pRow->col];
124 removeByUD(pRow);
125 }
126 removeByLR(pCol);
127 }
128 }
129 }
130
131 void resume(int _c)
132 {
133 if(_c >= 0 && _c < head.col)
134 {
135 for(DancingLinkNode* pCol = columns[_c].pU; pCol != &columns[_c]; pCol = pCol->pU)
136 {
137 if(pCol->col == head.col)
138 {
139 continue;
140 }
141 resumeByLR(pCol);
142 for(DancingLinkNode* pRow = pCol->pL; pRow != pCol; pRow = pRow->pL)
143 {
144 if(pRow->col == head.col)
145 {
146 continue;
147 }
148 ++size[pRow->col];
149 resumeByUD(pRow);
150 }
151 }
152 resumeByLR(&columns[_c]);
153 }
154 }
155
156
157 bool dfs(int _k)
158 {
159 if(head.pL == &head)
160 {
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 {
169 if(size[pNode->col] < minV)
170 {
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 {
178 ans[_k] = pNode->row;
179 pNode->pL->pR = pNode;
180 for(DancingLinkNode* pNode2 = pNode->pR; pNode2 != pNode; pNode2 = pNode2->pR)
181 {
182 cover(pNode2->col);
183 }
184 if(dfs(_k+1))
185 {
186 return true;
187 }
188 pNode->pR->pL = pNode;
189 for(DancingLinkNode* pNode2 = pNode->pL; pNode2 != pNode; pNode2 = pNode2->pL)
190 {
191 resume(pNode2->col);
192 }
193 pNode->pL->pR = pNode->pR;
194 }
195 resume(minVcol);
196 return false;
197 }
198
199 void Print()
200 {
201 for(DancingLinkNode* pRow = head.pD; pRow != &head; pRow = pRow->pD)
202 {
203 if(pRow->row == head.row)
204 {
205 continue;
206 }
207 for(DancingLinkNode* pCol = pRow->pR; pCol != pRow; pCol = pCol->pR)
208 {
209 if(pCol->col == head.col)
210 continue;
211 printf("(%d %d),",pCol->row,pCol->col);
212 }
213 printf("\n");
214 }
215 }
216};
217DancingLink DLX;
218char str[320];
219
220void Insert(int _r,int _c,int _k)
221{
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
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
236void PrintAns()
237{
238 int reAns[N][N];
239 for(int i = 0; i < DLX.len; ++i)
240 {
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 {
248 for(int j = 0; j < N; ++j)
249 {
250 printf("%d",reAns[i][j]);
251 }
252 }
253 printf("\n");
254}
255
256void Test()
257{
258 DLX.init(N*N*N,4*N*N);
259 for(int i = 0; i < N; ++i)
260 {
261 for(int j = 0; j < N; ++j)
262 {
263 if(str[i*N+j] == '.')
264 {
265 for(int k = 0; k < N; ++k)
266 {
267 Insert(i,j,k);
268 }
269 }
270 else
271 {
272 Insert(i,j,str[i*N+j]-'1');
273 }
274 }
275 }
276 if(DLX.dfs(0))
277 {
278 PrintAns();
279 }
280}
281
282int main()
283{
284 while(gets(str))
285 {
286 if(strcmp(str,"end") == 0)
287 break;
288 Test();
289 }
290 return 0;
291} 同理，3076如法炮制
posted on 2012-03-12 19:37
bennycen 閱讀(2045)
評論(3) 編輯 收藏 引用 所屬分類:
算法題解