xhSong's Blog

poj3074, DLX解数独源代码

2013年6月26日 20:49

原题
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include <cstdio>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <iterator>
#include <algorithm>
 
 
using namespace std;
 
 
int const N = 3;
int PN = N * N, QN = PN * PN;
 
/***最大行***/
#define MAXROW 1001
/***最大列***/
#define MAXCOL 1001
 
struct DancingLinksNode {
    /***结点所在的行列位置***/
    int r, c;
    /***结点的上下左右结点指针***/
    DancingLinksNode *U, *D, *L, *R;
};
 
/****备用结点****/
DancingLinksNode node[MAXROW * 101];
/****行头****/
DancingLinksNode row[MAXROW];
/****列头****/
DancingLinksNode col[MAXCOL];
/****表头****/
DancingLinksNode head;
/****使用了多少结点****/
int cnt;
/****列含有多少个域****/
int size[MAXCOL];
/****表的行与列变量****/
int m, n;
/****选择的行****/
int choice[MAXROW];
 
/****初始化，r, c分别表示表的大小***/
void init(int r, int c) {
    /****将可以使用的结点设为第一个****/
    cnt = 0;
    /****head结点的r,c分别表示表的大小,以备查****/
    head.r = r;
    head.c = c;
    /****初始化head结点****/
    head.L = head.R = head.U = head.D = &head;
 
    /***初始化列头***/
    for(int i = 0; i < c; ++i) {
        col[i].r = r;
        col[i].c = i;
        col[i].L = head.L;
        col[i].R = &head;
        col[i].L->R = col[i].R->L = &col[i];
        col[i].U = col[i].D = &col[i];
        size[i] = 0;
    }
 
 
    /***初始化行头,在删除的时候，如果碰到row[i].c  == c的情形应当被跳过***/
    for(int i = r - 1; i > -1; --i) {
        row[i].r = i;
        row[i].c = c;
        row[i].U = head.U;
        row[i].D = &head;
        row[i].U->D = row[i].D->U = &row[i];
        row[i].L = row[i].R = &row[i];
    }
}
 
/****增加一个结点,在原表中的位置为r行,c列***/
inline void addNode(int r, int c) {
    /****找一个未曾使用的结点****/
    DancingLinksNode *ptr = &node[cnt++];
 
    /****设置结点的行列号****/
    ptr->r = r;
    ptr->c = c;
 
    /****将结点加入双向链表中****/
    ptr->L = row[r].L;
    ptr->R = &row[r];
    ptr->L->R = ptr->R->L = ptr;
 
    ptr->U = col[c].U;
    ptr->D = &col[c];
    ptr->U->D = ptr->D->U = ptr;
 
    /****将size域加1****/
    ++size[c];
}
 
/****删除ptr所指向的结点的左右方向****/
inline void delLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R;
    ptr->R->L = ptr->L;
}
 
/****删除ptr所指向的结点的上下方向****/
inline void delUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D;
    ptr->D->U = ptr->U;
}
 
/****重置ptr所指向的结点的左右方向****/
inline void resumeLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R->L = ptr;
}
 
/****重置ptr所指向的结点的上下方向****/
inline void resumeUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D->U = ptr;
}
 
/****覆盖第c例***/
inline void cover(int c) {
    /**** c == n 表示头****/
    if(c == n) {
        return;
    }
 
    /****删除表头****/
    delLR(&col[c]);
 
    DancingLinksNode *R, *C;
    for(C = col[c].D; C != (&col[c]); C = C->D) {
        if(C->c == n)
            continue;
        for(R = C->L; R != C; R = R->L){
            if(R->c == n)
                continue;
            --size[R->c];
            delUD(R);
        }
        delLR(C);
    }
 
}
 
/****重置第c列****/
inline void resume(int c) {
    if(c == n)
        return;
    DancingLinksNode *R, *C;
    for(C = col[c].U; C != (&col[c]); C = C->U) {
        if(C->c == n)
            continue;
        resumeLR(C);
        for(R = C->R; R != C; R = R->R) {
            if(R->c == n)
                continue;
            ++size[R->c];
            resumeUD(R);
        }
    }
 
    /****把列头接进表头中****/
    resumeLR(&col[c]);
}
 
/****搜索核心算法,k表示搜索层数****/
int search(int k ＝ 0) {
 
    /***搜索成功,返回true***/
    if(head.L == (&head)) {
        return k;
    }
    /***c表示下一个列对象位置,找一个分支数目最小的进行覆盖***/
    int INF = (1<<30), c = -1;
 
    for(DancingLinksNode * ptr = head.L; ptr != (&head); ptr = ptr->L) {
        if(size[ptr->c] < INF) {
            INF = size[ptr->c];
            c = ptr->c;
        }
    }
    /***覆盖第c列***/
    cover(c);
 
    DancingLinksNode * ptr;
 
    for(ptr = col[c].D; ptr != (&col[c]); ptr = ptr->D) {
        DancingLinksNode *rc;
        ptr->R->L = ptr;
        choice[k] = ptr->r;
        for(rc = ptr->L; rc != ptr; rc = rc->L) {
            cover(rc->c);
        }
        ptr->R->L = ptr->L;
        int ans = search(k + 1);
        if(ans) {
            return ans;
        }
        ptr->L->R = ptr;
        for(rc = ptr->R; rc != ptr; rc = rc->R) {
            resume(rc->c);
        }
        ptr->L->R = ptr->R;
    }
 
    /***取消覆盖第c列***/
    resume(c);
    return 0;
}
 
 
void addPoss(int i, int j) {
    int x = i / PN, y = i % PN;
    addNode(i * PN + j, i);
    addNode(i * PN + j, QN * 1+ x * PN + j);
    addNode(i * PN + j, QN * 2 + y * PN + j);
    addNode(i * PN + j, QN * 3 + (x / N * N + y / N) * PN + j);
}
 
int main(int argc, char** argv) {
    char s[100];
    while(1) {
        scanf("%s", s);
        if(strcmp(s, "end") == 0) {
            break;
        }
        m = PN * QN, n = 4 * QN;
        init(m, n);
        for(int i = 0; i < QN; ++i) {
            if(s[i] == '.')  {
                for(int j = 0; j < PN; ++j) addPoss(i, j);
            } else {
                addPoss(i, s[i] - '1');
            }   
        }
        search();
        for(int i = 0; i < QN; i ++) {
            s[choice[i] / PN] = choice[i] % PN + '1';
        }
        puts(s);
    }
    return 0;
}
Posted by xhSong Filed in 搜索 Tagged by poj 3074 sudoku DLX Comments[1]
hustsxh

分类

最新评论

最新留言

链接

功能

poj3074, DLX解数独源代码

2013年6月26日 20:49
