代码
比这篇新的文章:
Codee#1739
比这篇旧的文章: Codee#1737
作者: 半瓶墨水, 点击3826次, 评论(26), 收藏者(1), , 打分:
所有评论，共26条：( 我也来说两句)
比这篇旧的文章: Codee#1737
目前最快的数独求解程序 - 实现了Knuth的Dancing Links+Algorithm X算法
语言: C++, 标签: 数独 求解 2009/06/02发布 2年前更新 更新记录作者: 半瓶墨水, 点击3826次, 评论(26), 收藏者(1), , 打分:
001 //from: http://code.google.com/p/klsudoku/source/checkout
002 //半瓶墨水修改于 2009 Sept 18
003 //References
004 // http://en.wikipedia.org/wiki/Knuth's_Algorithm_X
005 // http://en.wikipedia.org/wiki/Dancing_Links
006 // http://en.wikipedia.org/wiki/Exact_cover#Sudoku
007
008 #include<iostream>
009 using namespace std;
010 #define RR 729
011 #define CC 324
012 #define INF 1000000000
013 int mem1[81+1];
014 int mem2[81+1];
015 int *mem = mem1;
016 char ch[81+1];
017 int cnt[CC+1];
018 int scnt=0; //solution count
019
020 struct node {
021 int r,c;
022 node *up;
023 node *down;
024 node *left;
025 node *right;
026 }head,all[RR*CC+99],row[RR],col[CC];int all_t;
027
028 inline void link(int r,int c) {
029 cnt[c]++;
030 node *t=&all[all_t++];
031 t->r=r;
032 t->c=c;
033 t->left=&row[r];
034 t->right=row[r].right;
035 t->left->right=t;
036 t->right->left=t;
037 t->up=&col[c];
038 t->down=col[c].down;
039 t->up->down=t;
040 t->down->up=t;
041 }
042
043 inline void remove(int c) {
044 node *t,*tt;
045 col[c].right->left=col[c].left;
046 col[c].left->right=col[c].right;
047 for(t=col[c].down;t!=&col[c];t=t->down) {
048 for(tt=t->right;tt!=t;tt=tt->right) {
049 cnt[tt->c]--;
050 tt->up->down=tt->down;
051 tt->down->up=tt->up;
052 }
053 t->left->right=t->right;
054 t->right->left=t->left;
055 }
056 }
057
058 inline void resume(int c) {
059 node *t,*tt;
060 for(t=col[c].down;t!=&col[c];t=t->down) {
061 t->right->left=t;
062 t->left->right=t;
063 for(tt=t->left;tt!=t;tt=tt->left) {
064 cnt[tt->c]++;
065 tt->down->up=tt;
066 tt->up->down=tt;
067 }
068 }
069 col[c].left->right=&col[c];
070 col[c].right->left=&col[c];
071 }
072
073 void print_solution(int*m){
074 int ans[81];
075 for(int i=1;i<=81;i++) {
076 int t=m[i]/9%81;
077 int val=m[i]%9+1;
078 ans[t]=val;
079 }
080 for(int i=0;i<81;i++)
081 printf("%d",ans[i]);
082 printf("\n");
083 }
084
085 void solve(int k)
086 {
087 if(head.right==&head) {//got one solution
088 if (!scnt) {
089 memcpy(mem2, mem1, sizeof(mem1));
090 mem = mem2;
091 }
092 scnt++;
093 return;
094 }
095 node*t,*tt;
096 int min=INF,tc;
097 for(t=head.right;t!=&head;t=t->right) {
098 if(cnt[t->c]<min) {
099 min=cnt[t->c];
100 tc=t->c;
101 if(min<=1)break;
102 }
103 }
104 remove(tc);
105 for(t=col[tc].down;t!=&col[tc];t=t->down) {
106 mem[k]=t->r;
107 t->left->right=t;
108 for(tt=t->right;tt!=t;tt=tt->right) {
109 remove(tt->c);
110 }
111 t->left->right=t->right;
112 solve(k+1);
113 if (scnt >= 2)
114 return;
115 t->right->left=t;
116 for(tt=t->left;tt!=t;tt=tt->left) {
117 resume(tt->c);
118 }
119 t->right->left=t->left;
120 }
121 resume(tc);
122 return;
123 }
124
125 int main(int argc, char**argv) {
126 if (argc != 2) return 1;
127 const char *p = argv[1];
128 size_t len = strlen(p);
129 if (len!=81) return 1;
130 int i,j,k;
131 for (i=0;i<81;i++) {
132 if ((*p) == '0')
133 ch[i] = '.';
134 else
135 ch[i] = *p;
136 p++;
137 }
138 ch[81] = '\0';
139
140 if(ch[0]=='e')return 1;
141 all_t=1;
142 memset(cnt,0,sizeof(cnt));
143 head.left=&head;
144 head.right=&head;
145 head.up=&head;
146 head.down=&head;
147 head.r=RR;
148 head.c=CC;
149 for(i=0;i<CC;i++) {
150 col[i].c=i;
151 col[i].r=RR;
152 col[i].up=&col[i];
153 col[i].down=&col[i];
154 col[i].left=&head;
155 col[i].right=head.right;
156 col[i].left->right=&col[i];
157 col[i].right->left=&col[i];
158 }
159 for(i=0;i<RR;i++) {
160 row[i].r=i;
161 row[i].c=CC;
162 row[i].left=&row[i];
163 row[i].right=&row[i];
164 row[i].up=&head;
165 row[i].down=head.down;
166 row[i].up->down=&row[i];
167 row[i].down->up=&row[i];
168 }
169 for(i=0;i<RR;i++) {
170 int r=i/9/9%9;
171 int c=i/9%9;
172 int val=i%9+1;
173 if(ch[r*9+c]=='.'||ch[r*9+c]==val+'0') {
174 link(i,r*9+val-1);
175 link(i,81+c*9+val-1);
176 int tr=r/3;
177 int tc=c/3;
178 link(i,162+(tr*3+tc)*9+val-1);
179 link(i,243+r*9+c);
180 }
181 }
182 for(i=0;i<RR;i++) {
183 row[i].left->right=row[i].right;
184 row[i].right->left=row[i].left;
185 }
186 solve(1);
187 printf("\n");
188 if (scnt>1){
189 print_solution(mem1);
190 print_solution(mem2);
191 printf("\n2 or mroe solutions found\n");
192 } else if (scnt==1) {
193 print_solution(mem1);
194 printf("\none solution found\n");
195 } else {
196 printf("\nNO solution\n");
197 }
198 }
002 //半瓶墨水修改于 2009 Sept 18
003 //References
004 // http://en.wikipedia.org/wiki/Knuth's_Algorithm_X
005 // http://en.wikipedia.org/wiki/Dancing_Links
006 // http://en.wikipedia.org/wiki/Exact_cover#Sudoku
007
008 #include<iostream>
009 using namespace std;
010 #define RR 729
011 #define CC 324
012 #define INF 1000000000
013 int mem1[81+1];
014 int mem2[81+1];
015 int *mem = mem1;
016 char ch[81+1];
017 int cnt[CC+1];
018 int scnt=0; //solution count
019
020 struct node {
021 int r,c;
022 node *up;
023 node *down;
024 node *left;
025 node *right;
026 }head,all[RR*CC+99],row[RR],col[CC];int all_t;
027
028 inline void link(int r,int c) {
029 cnt[c]++;
030 node *t=&all[all_t++];
031 t->r=r;
032 t->c=c;
033 t->left=&row[r];
034 t->right=row[r].right;
035 t->left->right=t;
036 t->right->left=t;
037 t->up=&col[c];
038 t->down=col[c].down;
039 t->up->down=t;
040 t->down->up=t;
041 }
042
043 inline void remove(int c) {
044 node *t,*tt;
045 col[c].right->left=col[c].left;
046 col[c].left->right=col[c].right;
047 for(t=col[c].down;t!=&col[c];t=t->down) {
048 for(tt=t->right;tt!=t;tt=tt->right) {
049 cnt[tt->c]--;
050 tt->up->down=tt->down;
051 tt->down->up=tt->up;
052 }
053 t->left->right=t->right;
054 t->right->left=t->left;
055 }
056 }
057
058 inline void resume(int c) {
059 node *t,*tt;
060 for(t=col[c].down;t!=&col[c];t=t->down) {
061 t->right->left=t;
062 t->left->right=t;
063 for(tt=t->left;tt!=t;tt=tt->left) {
064 cnt[tt->c]++;
065 tt->down->up=tt;
066 tt->up->down=tt;
067 }
068 }
069 col[c].left->right=&col[c];
070 col[c].right->left=&col[c];
071 }
072
073 void print_solution(int*m){
074 int ans[81];
075 for(int i=1;i<=81;i++) {
076 int t=m[i]/9%81;
077 int val=m[i]%9+1;
078 ans[t]=val;
079 }
080 for(int i=0;i<81;i++)
081 printf("%d",ans[i]);
082 printf("\n");
083 }
084
085 void solve(int k)
086 {
087 if(head.right==&head) {//got one solution
088 if (!scnt) {
089 memcpy(mem2, mem1, sizeof(mem1));
090 mem = mem2;
091 }
092 scnt++;
093 return;
094 }
095 node*t,*tt;
096 int min=INF,tc;
097 for(t=head.right;t!=&head;t=t->right) {
098 if(cnt[t->c]<min) {
099 min=cnt[t->c];
100 tc=t->c;
101 if(min<=1)break;
102 }
103 }
104 remove(tc);
105 for(t=col[tc].down;t!=&col[tc];t=t->down) {
106 mem[k]=t->r;
107 t->left->right=t;
108 for(tt=t->right;tt!=t;tt=tt->right) {
109 remove(tt->c);
110 }
111 t->left->right=t->right;
112 solve(k+1);
113 if (scnt >= 2)
114 return;
115 t->right->left=t;
116 for(tt=t->left;tt!=t;tt=tt->left) {
117 resume(tt->c);
118 }
119 t->right->left=t->left;
120 }
121 resume(tc);
122 return;
123 }
124
125 int main(int argc, char**argv) {
126 if (argc != 2) return 1;
127 const char *p = argv[1];
128 size_t len = strlen(p);
129 if (len!=81) return 1;
130 int i,j,k;
131 for (i=0;i<81;i++) {
132 if ((*p) == '0')
133 ch[i] = '.';
134 else
135 ch[i] = *p;
136 p++;
137 }
138 ch[81] = '\0';
139
140 if(ch[0]=='e')return 1;
141 all_t=1;
142 memset(cnt,0,sizeof(cnt));
143 head.left=&head;
144 head.right=&head;
145 head.up=&head;
146 head.down=&head;
147 head.r=RR;
148 head.c=CC;
149 for(i=0;i<CC;i++) {
150 col[i].c=i;
151 col[i].r=RR;
152 col[i].up=&col[i];
153 col[i].down=&col[i];
154 col[i].left=&head;
155 col[i].right=head.right;
156 col[i].left->right=&col[i];
157 col[i].right->left=&col[i];
158 }
159 for(i=0;i<RR;i++) {
160 row[i].r=i;
161 row[i].c=CC;
162 row[i].left=&row[i];
163 row[i].right=&row[i];
164 row[i].up=&head;
165 row[i].down=head.down;
166 row[i].up->down=&row[i];
167 row[i].down->up=&row[i];
168 }
169 for(i=0;i<RR;i++) {
170 int r=i/9/9%9;
171 int c=i/9%9;
172 int val=i%9+1;
173 if(ch[r*9+c]=='.'||ch[r*9+c]==val+'0') {
174 link(i,r*9+val-1);
175 link(i,81+c*9+val-1);
176 int tr=r/3;
177 int tc=c/3;
178 link(i,162+(tr*3+tc)*9+val-1);
179 link(i,243+r*9+c);
180 }
181 }
182 for(i=0;i<RR;i++) {
183 row[i].left->right=row[i].right;
184 row[i].right->left=row[i].left;
185 }
186 solve(1);
187 printf("\n");
188 if (scnt>1){
189 print_solution(mem1);
190 print_solution(mem2);
191 printf("\n2 or mroe solutions found\n");
192 } else if (scnt==1) {
193 print_solution(mem1);
194 printf("\none solution found\n");
195 } else {
196 printf("\nNO solution\n");
197 }
198 }
所有评论，共26条：( 我也来说两句)
| 1 |
winxos
2年前
回复
竟然这么短就实现了，强！
|
| 2 |
注：发现该算法的一个bug - 求解下面这个布局的时候结果不正确
|
| 3 |
@半瓶墨水: 终于知道是啥问题了，scnt+=solve的地方返回就行了，或者改巴改巴也可以打出所有解
|
| 4 |
已经改好，现在可以显示多解、无解、唯一解，并且加上了参考链接
|
| 5 |
高人啊，我对你这个dancing link很感兴趣啊，但是本人技术不好，尝试改出输出所有解，但是不成
|
| 6 |
@snakech: 应该是已经改好了啊，你试试看
|
| 7 |
njuaplusplus
3个月前
回复
楼主 您好！
|
| 8 |
@njuaplusplus:
|
| 9 |
njuaplusplus
3个月前
回复
@半瓶墨水:
|
| 10 |
@njuaplusplus: 具体数字你可以再研究研究。还有，你说的对，mem1不用复制
|
| 11 |
lazycat007
2个月前
回复
你好，算法看了一部分，基本上看明白了，不过有个小问题想问一下：
|
| 12 |
lazycat007
1个月前
回复
算法全部研究完毕，这个算法如果想解决杀手数独还是力有不逮，需要进行改进，暂时没有思路。
|
| 13 |
njuaplusplus
1个月前
回复
@lazycat007: 不叫这个算法，应该是这个程序是解不了杀手数独的，如果按照算法来说的话，加入相关限制，应该是可以解杀手数独的，而且复杂度应该和解单纯的数独在一个数量级上的
|
| 14 |
njuaplusplus
1个月前
回复
@半瓶墨水: 这个程序存在致命的错误。。。可能会永远计算不出结果。。。
|
| 15 |
@njuaplusplus: 你能说说是哪个开局吗？我用这个程序计算过网上十万多个开局，都很好的呀
|
| 16 |
lazycat007
1个月前
回复
这个算法可以解决杀手数独，只要把行的内容修改了，就可以实现杀手数独的解题，而且速度很快。
|
| 17 |
lazycat007
1个月前
回复
@njuaplusplus: 我知道你说的致命错误了，那个不是程序的错误，而是A*搜索算法本身的弱点。这个KNUTH在他关于A*搜索算法的文章中提到过，就是当我制造一个很明显的错误，使题目无解时，算法可能需要遍历整个搜索树，才能告诉我无解。
|
| 18 |
lazycat007
1个月前
回复
@njuaplusplus: 之前是我没有完全理解算法，所以才会那么说。当我实现了杀手数独的解题后，才对这个算法有了新的认识。这个程序只是实现了对普通数独的解题，对于杀手数独，因为缺少限制条件，完全没有办法，只能遍历。
|
| 19 |
lazycat007
1个月前
回复
关于11楼的那几行，我看过文章后知道，应该是用left才对，要完全反序恢复嘛。
|
| 20 |
njuaplusplus
1个月前
回复
@半瓶墨水: 不好意思。。之前在赶作业。。所以没有回复。。这个回复好像没有提醒功能呢~
|
| 21 |
njuaplusplus
1个月前
回复
@lazycat007: 请问你是怎么用这个来改杀手数独的呢~
|
| 22 |
lazycat007
1个月前
回复
@njuaplusplus: 你说的这个问题应该不存在，本身算法就是可回溯的，必须要在函数返回后，将删除的结点进行恢复。因为函数在挑选列时，每次只找一个CNT最少的列，然后对这一列进行循环，所以每次函数返回，就会选择该列的下一个结点，也即下一种可能，因此不会有重复。现在这段代码只能显示2个解，需要稍微修改下，才能显示更多的解。
|
| 23 |
lazycat007
1个月前
回复
|
| 24 |
lazycat007
1个月前
回复
其中需要注意的是，如果是9区块，可以按照普通数独的方法设置，将9个候选数都设置进去即可。并且在行头上记录该行是哪些位置上有哪些候选数。在解题时，每选择一行，就记录该行对应的位置和候选数。
|
| 25 |
lazycat007
1个月前
回复
@njuaplusplus: 请仔细看105~120行的代码。并请仔细检查得出的结果。
|
| 26 |
lazycat007
1个月前
回复
其实是代码写得太烂，不好意思往上发。
|