题意:求解数独问题。
思路:用DLX解。首先,需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种,因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列,也即总共是9*9+9*9+9*9+9*9=324个链表列,十字链表中每一行表示在某格点放置某数,分别与4个对应的链表列相交。
然后,就是正式的深搜了。在深搜的每一层:
1) 在十字链表表头中找出元素最少且非零的一列,将该列以及列中包含的所有行元素从十字链表中移除;
2) 枚举列中的每行(作为解的一部分),将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除,递归下一层深搜;
3) 递归返回时,需要将2)中移除的相应列和行添加回十字链表;
4) 所有行枚举完毕时,需要将1)中移除的相应列和行添加回十字链表。
注意,对链表进行增删操作时,需要以相反的顺序修改各结点。同时,也需要动态维护表头的元素数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 |
#include<cstdio> #include<cstring> #define M 10000 int s[9][9],sl; int hd,el,tag; char t[82],r[9][10],c[9][10],b[9][10]; struct E { int l,r,u,d,c,s; int ri,ci,bi,v; }e[M]; void adde(int ei,int ri,int ci,int bi,int v) { e[ei].s++; e[el].u=ei; e[el].d=e[ei].d; e[e[ei].d].u=el; e[ei].d=el; e[el].c=ei; e[el].ri=ri; e[el].ci=ci; e[el].bi=bi; e[el].v=v; el++; } void addr(int ri,int ci,int bi,int v) { int i,j,k,l; adde(1+ri*9+v-1,ri,ci,bi,v); adde(1+81+ci*9+v-1,ri,ci,bi,v); adde(1+81+81+bi*9+v-1,ri,ci,bi,v); adde(1+81+81+81+ri*9+ci,ri,ci,bi,v); for(i=0;i<4;i++) { j=(i+3)%4; k=(i+1)%4; e[el-4+i].l=el-4+j; e[el-4+i].r=el-4+k; } } void init() { int i,j,k,l,tl; hd=el=tag=0; sl=81; memset(r,0,sizeof r); memset(c,0,sizeof c); memset(b,0,sizeof b); for(i=tl=0;i<9;i++) { for(j=0;j<9;j++) { if(t[tl]=='.') k=0; else k=t[tl]-'0'; if(k) sl--; r[i][k]=1; c[j][k]=1; s[i][j]=k; l=i/3*3+j/3; b[l][k]=1; tl++; } } e[el].l=e[el].r=el; el++; for(i=0;i<324;i++) { e[el].l=hd; e[el].r=e[hd].r; e[e[hd].r].l=el; e[hd].r=el; e[el].u=e[el].d=e[el].c=el; e[el].s=0; el++; } for(i=0;i<9;i++) { for(j=0;j<9;j++) { if(s[i][j]) continue; l=i/3*3+j/3; for(k=1;k<10;k++) { if(r[i][k]||c[j][k]||b[l][k]) continue; addr(i,j,l,k); } } } } void pnt() { int i,j,tl; for(i=tl=0;i<9;i++) for(j=0;j<9;j++) t[tl++]='0'+s[i][j]; puts(t); } void dfs(int si) { if(si==sl) { tag=1; pnt(); return; } int i,j,k,l; int ii,jj,kk; int ri,ci,bi,v; for(i=e[hd].r,j=0x7fffffff;i!=hd;i=e[i].r) { if(e[i].s&&e[i].s<j) { j=e[i].s; k=i; } if(j==1) break; } if(j==0x7fffffff) return; e[e[k].l].r=e[k].r; e[e[k].r].l=e[k].l; for(i=e[k].d;i!=k;i=e[i].d) { for(j=e[i].r;j!=i;j=e[j].r) { e[e[j].c].s--; e[e[j].u].d=e[j].d; e[e[j].d].u=e[j].u; } } for(i=e[k].d;i!=k;i=e[i].d) { ri=e[i].ri; ci=e[i].ci; bi=e[i].bi; v=e[i].v; for(j=e[i].r;j!=i;j=e[j].r) { kk=e[j].c; e[e[kk].l].r=e[kk].r; e[e[kk].r].l=e[kk].l; for(ii=e[kk].d;ii!=kk;ii=e[ii].d) { for(jj=e[ii].r;jj!=ii;jj=e[jj].r) { e[e[jj].c].s--; e[e[jj].u].d=e[jj].d; e[e[jj].d].u=e[jj].u; } } } s[ri][ci]=v; dfs(si+1); if(tag) return; for(j=e[i].l;j!=i;j=e[j].l) { kk=e[j].c; e[e[kk].l].r=kk; e[e[kk].r].l=kk; for(ii=e[kk].u;ii!=kk;ii=e[ii].u) { for(jj=e[ii].l;jj!=ii;jj=e[jj].l) { e[e[jj].u].d=jj; e[e[jj].d].u=jj; e[e[jj].c].s++; } } } } for(i=e[k].u;i!=k;i=e[i].u) { for(j=e[i].l;j!=i;j=e[j].l) { e[e[j].u].d=j; e[e[j].d].u=j; e[e[j].c].s++; } } e[e[k].l].r=k; e[e[k].r].l=k; } void solve() { dfs(0); } int main() { while(scanf("%s",t)&&t[0]!='e') { init(); solve(); } return 0; } |
没有想出太好的优化。c++下跑了188ms。
ps:
记得最早是11年寒假时,和Arios一起留校做MCM时听他提到,当时那道建模题可以用Dancing Links解。一晃眼,3年多过去了,我这才开始读Knuth的这篇论文。
文章本身的算法不算难懂,因为深搜的优化是很多问题都要用到的。之前做题的时候,确实也有考虑过对链表进行动态调整,但发现无法根本上降低时间复杂度(依然是指数时间)后,也没有深究了。而Knuth这篇论文里介绍的DLX,通过对十字链表进行动态调整从而尽量保持搜索树最优,可以说是在通常情况下将深搜优化到了极致。
做这题数独时,在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系,发现表头记录的元素数无法正确维护,每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后,又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。
查了下status,Arios在5年前作出的时间是32ms,并且是1A 47ms过的。实在是很强。