首页 > 代码库 > dancing link 学习资源导航+心得
dancing link 学习资源导航+心得
dancing link简直是求解数独的神器，NOIP2009最后一题靶形数独，DFS 各种改变搜索顺序 都没法过，最后还是用了卡时过得。用dancing link写，秒杀所有数据，总时间才400ms不到。。（虽然还不是很清楚为什么会快）。
一开始还是先看这个blog，图文都非常清晰
http://www.cnblogs.com/grenet/p/3145800.html
上文解释了dancing link的原理，可以用来解决精度覆盖问题，但是求解数独问题还需要一步转化。
见博文：
http://www.cnblogs.com/grenet/p/3163550.html
大致思想是：
1、先遍历数独的格子，把那些有数字的格子转换为行，插入到矩阵中。在插入的同时，把包含1的列的列首元素的Count分量设置为-1（起到后面判别的作用）。
由于这些行一定能被选中，是答案的一部分，那么把这些行的行号置入到答案列表中，并把这些列的列首元素从水平双向链中移除（手动移除比调用RemoveCol方法快）
2、在遍历没有数字的格子，转换为若干行（1个格子9行）插入到矩阵中。在插入到矩阵的时候，判断包含1的列的列首元素的Count分量。如果是-1，说明新插入的行和第1步中的某些行相冲，是个无效行，没有必要插入到矩阵中；如果不是-1，说明是个有效行，插入到矩阵中。
这样把就数独转化成一个729*324的精度覆盖问题；
看了这个大致有些明白，但要是自己写还是无从下手，先看一个模板（注释比较清晰易懂）：
http://blog.csdn.net/weiguang_123/article/details/7935003
看完后可以尝试着做一做裸的精度覆盖问题poj3740，然后再去做靶形数独。
另外第一篇文章中有个地方：
在函数中有个很聪明的设计，在标示列首元素时，顺序是从I元素的右侧元素开始；而在回标列首元素时，顺序是从I元素的左侧元素开始，正好顺序和标示列首元素的顺序相反。
这里非常关键，本来以为无关紧要，把poj3740的代码 顺序改成一样，还是能AC，不过时间慢了一半， 还以为这是个优化时间的地方。但是把靶形数独的代码改成这样，就WA了一半的点，手工模拟下可以发现这个顺序问题不是可有可无的，而是必须的。
贴上我靶形数独的AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<iomanip> 7 using namespace std; 8 9 const int n=729,m=324; 10 bool mx[2000][2000]; 11 int map[10][10],cnt[2000],head,cur,ans; 12 int sqr[10][10]={{0,0,0,0,0,0,0,0,0,0}, 13 {0,1,1,1,4,4,4,7,7,7}, 14 {0,1,1,1,4,4,4,7,7,7}, 15 {0,1,1,1,4,4,4,7,7,7}, 16 {0,2,2,2,5,5,5,8,8,8}, 17 {0,2,2,2,5,5,5,8,8,8}, 18 {0,2,2,2,5,5,5,8,8,8}, 19 {0,3,3,3,6,6,6,9,9,9}, 20 {0,3,3,3,6,6,6,9,9,9}, 21 {0,3,3,3,6,6,6,9,9,9}}; 22 23 int w[10][10]={{0,0,0,0,0,0,0,0,0,0}, 24 {0,6,6,6,6,6,6,6,6,6}, 25 {0,6,7,7,7,7,7,7,7,6}, 26 {0,6,7,8,8,8,8,8,7,6}, 27 {0,6,7,8,9,9,9,8,7,6}, 28 {0,6,7,8,9,10,9,8,7,6}, 29 {0,6,7,8,9,9,9,8,7,6}, 30 {0,6,7,8,8,8,8,8,7,6}, 31 {0,6,7,7,7,7,7,7,7,6}, 32 {0,6,6,6,6,6,6,6,6,6}}; 33 34 struct point 35 { 36 int row,lc,rc,up,down,col; 37 }node[2000*2000]; 38 39 inline int id(int x,int y) 40 { 41 return (x-1)*9+y; 42 } 43 44 void init(int c) 45 { 46 for (int i=0;i<=c;i++) 47 { 48 node[i].lc=i-1; 49 node[i].rc=i+1; 50 node[i].up=node[i].down=node[i].col=i; 51 } 52 node[0].lc=c; 53 node[c].rc=0; 54 } 55 56 void build_link() 57 { 58 cur=m; 59 for (int i=1;i<=n;i++) 60 { 61 int start,pre; 62 start=pre=cur+1; 63 for (int j=1;j<=m;j++) 64 if (mx[i][j]) 65 { 66 cur++; 67 cnt[j]++; 68 node[cur].row=i; 69 70 node[cur].lc=pre; 71 node[cur].rc=start; 72 node[pre].rc=cur; 73 node[start].lc=cur; 74 75 node[cur].col=j; 76 node[cur].up=node[j].up; 77 node[cur].down=j; 78 node[node[j].up].down=cur; 79 node[j].up=cur; 80 pre=cur; 81 } 82 } 83 } 84 85 inline void cover(int c) 86 { 87 for (int i=node[c].up;i!=c;i=node[i].up) 88 for (int j=node[i].rc;j!=i;j=node[j].rc) 89 { 90 node[node[j].up].down=node[j].down; 91 node[node[j].down].up=node[j].up; 92 cnt[node[j].col]--; 93 } 94 node[node[c].lc].rc=node[c].rc; 95 node[node[c].rc].lc=node[c].lc; 96 } 97 98 inline void uncover(int c) 99 {100 for (int i=node[c].up;i!=c;i=node[i].up)101 for (int j=node[i].rc;j!=i;j=node[j].rc)102 {103 node[node[j].up].down=j;104 node[node[j].down].up=j;105 cnt[node[j].col]++;106 }107 node[node[c].lc].rc=c;108 node[node[c].rc].lc=c;109 }110 111 void read_data()112 {113 for (int i=1;i<=9;i++)114 for (int j=1;j<=9;j++)115 {116 scanf("%d",&map[i][j]);117 int c=id(i,j),t,k;118 if (map[i][j])119 {120 k=map[i][j];121 t=(c-1)*9+k;122 mx[t][c]=true;123 mx[t][81+9*(i-1)+k]=true;124 mx[t][162+9*(j-1)+k]=true;125 mx[t][243+(sqr[i][j]-1)*9+k]=true;126 }127 else128 {129 for (k=1;k<=9;k++)130 {131 t=(c-1)*9+k;132 mx[t][c]=true;133 mx[t][81+9*(i-1)+k]=true;134 mx[t][162+9*(j-1)+k]=true;135 mx[t][243+(sqr[i][j]-1)*9+k]=true;136 }137 }138 }139 }140 141 bool dfs(int step,int score)142 {143 if (node[head].rc==head)144 {145 ans=max(score,ans);146 return true;147 }148 149 int i,j,c,t=210000,x,y,num,flag=0;150 for (i=node[head].rc;i!=head;i=node[i].rc)151 if (cnt[i]<t)152 {153 t=cnt[i];154 c=i;155 }156 if (t==0)157 return false;158 cover(c);159 160 for (i=node[c].down;i!=c;i=node[i].down)161 {162 for (j=node[i].lc;j!=i;j=node[j].lc)163 cover(node[j].col);164 num=(node[i].row-1)/9+1;165 x=(num-1)/9+1;166 y=num-9*(x-1);167 flag|=dfs(step+1,score+w[x][y]*(node[i].row-(num-1)*9));168 for (j=node[i].rc;j!=i;j=node[j].rc)169 uncover(node[j].col);170 }171 172 uncover(c);173 return flag;174 }175 176 void solve()177 {178 init(m);179 build_link();180 int flag=1;181 if (!dfs(1,0))182 printf("-1\n");183 else printf("%d\n",ans);184 }185 186 int main()187 {188 //freopen("in.in","r",stdin);189 //freopen("out.out","w",stdout);190 read_data();191 solve();192 return 0;193 }
如果要输出数独填好之后的结果，且数独的解唯一,代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<iomanip> 7 using namespace std; 8 9 const int n=729,m=324; 10 bool mx[2000][2000]; 11 int map[10][10],cnt[2000],head,cur,ans[10][10]; 12 int sqr[10][10]={{0,0,0,0,0,0,0,0,0,0}, 13 {0,1,1,1,4,4,4,7,7,7}, 14 {0,1,1,1,4,4,4,7,7,7}, 15 {0,1,1,1,4,4,4,7,7,7}, 16 {0,2,2,2,5,5,5,8,8,8}, 17 {0,2,2,2,5,5,5,8,8,8}, 18 {0,2,2,2,5,5,5,8,8,8}, 19 {0,3,3,3,6,6,6,9,9,9}, 20 {0,3,3,3,6,6,6,9,9,9}, 21 {0,3,3,3,6,6,6,9,9,9}}; 22 23 struct point 24 { 25 int row,lc,rc,up,down,col; 26 }node[2000*2000]; 27 28 inline int id(int x,int y) 29 { 30 return (x-1)*9+y; 31 } 32 33 void init(int c) 34 { 35 for (int i=0;i<=c;i++) 36 { 37 node[i].lc=i-1; 38 node[i].rc=i+1; 39 node[i].up=node[i].down=node[i].col=i; 40 } 41 node[0].lc=c; 42 node[c].rc=0; 43 } 44 45 void build_link() 46 { 47 cur=m; 48 for (int i=1;i<=n;i++) 49 { 50 int start,pre; 51 start=pre=cur+1; 52 for (int j=1;j<=m;j++) 53 if (mx[i][j]) 54 { 55 cur++; 56 cnt[j]++; 57 node[cur].row=i; 58 59 node[cur].lc=pre; 60 node[cur].rc=start; 61 node[pre].rc=cur; 62 node[start].lc=cur; 63 64 node[cur].col=j; 65 node[cur].up=node[j].up; 66 node[cur].down=j; 67 node[node[j].up].down=cur; 68 node[j].up=cur; 69 pre=cur; 70 } 71 } 72 } 73 74 inline void cover(int c) 75 { 76 for (int i=node[c].up;i!=c;i=node[i].up) 77 for (int j=node[i].rc;j!=i;j=node[j].rc) 78 { 79 node[node[j].up].down=node[j].down; 80 node[node[j].down].up=node[j].up; 81 cnt[node[j].col]--; 82 } 83 node[node[c].lc].rc=node[c].rc; 84 node[node[c].rc].lc=node[c].lc; 85 } 86 87 inline void uncover(int c) 88 { 89 for (int i=node[c].up;i!=c;i=node[i].up) 90 for (int j=node[i].rc;j!=i;j=node[j].rc) 91 { 92 node[node[j].up].down=j; 93 node[node[j].down].up=j; 94 cnt[node[j].col]++; 95 } 96 node[node[c].lc].rc=c; 97 node[node[c].rc].lc=c; 98 } 99 100 void read_data()101 {102 for (int i=1;i<=9;i++)103 for (int j=1;j<=9;j++)104 {105 char g;106 scanf(" %c",&g);107 map[i][j]=(int)g-‘0‘;108 int c=id(i,j),t,k;109 if (map[i][j])110 {111 k=map[i][j];112 t=(c-1)*9+k;113 mx[t][c]=true;114 mx[t][81+9*(i-1)+k]=true;115 mx[t][162+9*(j-1)+k]=true;116 mx[t][243+(sqr[i][j]-1)*9+k]=true;117 }118 else119 {120 for (k=1;k<=9;k++)121 {122 t=(c-1)*9+k;123 mx[t][c]=true;124 mx[t][81+9*(i-1)+k]=true;125 mx[t][162+9*(j-1)+k]=true;126 mx[t][243+(sqr[i][j]-1)*9+k]=true;127 }128 }129 }130 }131 132 void print()133 {134 for (int i=1;i<=9;i++)135 {136 for (int j=1;j<=9;j++)137 printf("%d",ans[i][j]);138 printf("\n");139 }140 }141 142 bool dfs(int step)143 {144 if (node[head].rc==head)145 {146 print();147 return true;148 }149 150 int i,j,c,t=210000,x,y,num,flag=0;151 for (i=node[head].rc;i!=head;i=node[i].rc)152 if (cnt[i]<t)153 {154 t=cnt[i];155 c=i;156 }157 if (t==0)158 return false;159 cover(c);160 161 for (i=node[c].down;i!=c;i=node[i].down)162 {163 for (j=node[i].lc;j!=i;j=node[j].lc)164 cover(node[j].col);165 num=(node[i].row-1)/9+1;166 x=(num-1)/9+1;167 y=num-9*(x-1);168 ans[x][y]=node[i].row-(num-1)*9;169 if (dfs(step+1))170 return true;171 for (j=node[i].rc;j!=i;j=node[j].rc)172 uncover(node[j].col);173 }174 175 uncover(c);176 return false;177 }178 179 void solve()180 {181 init(m);182 build_link();183 if (!dfs(1))184 printf("-1\n");185 }186 187 int main()188 {189 freopen("alone.in","r",stdin);190 freopen("alone.out","w",stdout);191 read_data();192 solve();193 return 0;194 }
dancing link 学习资源导航+心得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。