posts - 33,  comments - 33,  trackbacks - 0
数独问题
采用跳舞链方法会得到比较快的速度
用跳舞链解决的方法主要是将问题的模型转换成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*_r + _k;
229    DLX.addNode(R,C);
230    C = 2*N*+ N*_c + _k;
231    DLX.addNode(R,C);
232    C = 3*N*+ N*+ _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*- 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 阅读(1956) 评论(3)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理