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代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std; const int n=,m=;
bool mx[][];
int map[][],cnt[],head,cur,ans;
int sqr[][]={{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}}; int w[][]={{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}}; struct point
{
int row,lc,rc,up,down,col;
}node[*]; inline int id(int x,int y)
{
return (x-)*+y;
} void init(int c)
{
for (int i=;i<=c;i++)
{
node[i].lc=i-;
node[i].rc=i+;
node[i].up=node[i].down=node[i].col=i;
}
node[].lc=c;
node[c].rc=;
} void build_link()
{
cur=m;
for (int i=;i<=n;i++)
{
int start,pre;
start=pre=cur+;
for (int j=;j<=m;j++)
if (mx[i][j])
{
cur++;
cnt[j]++;
node[cur].row=i; node[cur].lc=pre;
node[cur].rc=start;
node[pre].rc=cur;
node[start].lc=cur; node[cur].col=j;
node[cur].up=node[j].up;
node[cur].down=j;
node[node[j].up].down=cur;
node[j].up=cur;
pre=cur;
}
}
} inline void cover(int c)
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=node[j].down;
node[node[j].down].up=node[j].up;
cnt[node[j].col]--;
}
node[node[c].lc].rc=node[c].rc;
node[node[c].rc].lc=node[c].lc;
} inline void uncover(int c)
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=j;
node[node[j].down].up=j;
cnt[node[j].col]++;
}
node[node[c].lc].rc=c;
node[node[c].rc].lc=c;
} void read_data()
{
for (int i=;i<=;i++)
for (int j=;j<=;j++)
{
scanf("%d",&map[i][j]);
int c=id(i,j),t,k;
if (map[i][j])
{
k=map[i][j];
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
else
{
for (k=;k<=;k++)
{
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
}
}
} bool dfs(int step,int score)
{
if (node[head].rc==head)
{
ans=max(score,ans);
return true;
} int i,j,c,t=,x,y,num,flag=;
for (i=node[head].rc;i!=head;i=node[i].rc)
if (cnt[i]<t)
{
t=cnt[i];
c=i;
}
if (t==)
return false;
cover(c); for (i=node[c].down;i!=c;i=node[i].down)
{
for (j=node[i].lc;j!=i;j=node[j].lc)
cover(node[j].col);
num=(node[i].row-)/+;
x=(num-)/+;
y=num-*(x-);
flag|=dfs(step+,score+w[x][y]*(node[i].row-(num-)*));
for (j=node[i].rc;j!=i;j=node[j].rc)
uncover(node[j].col);
} uncover(c);
return flag;
} void solve()
{
init(m);
build_link();
int flag=;
if (!dfs(,))
printf("-1\n");
else printf("%d\n",ans);
} int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
read_data();
solve();
return ;
}
如果要输出数独填好之后的结果，且数独的解唯一,代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std; const int n=,m=;
bool mx[][];
int map[][],cnt[],head,cur,ans[][];
int sqr[][]={{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}}; struct point
{
int row,lc,rc,up,down,col;
}node[*]; inline int id(int x,int y)
{
return (x-)*+y;
} void init(int c)
{
for (int i=;i<=c;i++)
{
node[i].lc=i-;
node[i].rc=i+;
node[i].up=node[i].down=node[i].col=i;
}
node[].lc=c;
node[c].rc=;
} void build_link()
{
cur=m;
for (int i=;i<=n;i++)
{
int start,pre;
start=pre=cur+;
for (int j=;j<=m;j++)
if (mx[i][j])
{
cur++;
cnt[j]++;
node[cur].row=i; node[cur].lc=pre;
node[cur].rc=start;
node[pre].rc=cur;
node[start].lc=cur; node[cur].col=j;
node[cur].up=node[j].up;
node[cur].down=j;
node[node[j].up].down=cur;
node[j].up=cur;
pre=cur;
}
}
} inline void cover(int c)
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=node[j].down;
node[node[j].down].up=node[j].up;
cnt[node[j].col]--;
}
node[node[c].lc].rc=node[c].rc;
node[node[c].rc].lc=node[c].lc;
} inline void uncover(int c)
{
for (int i=node[c].up;i!=c;i=node[i].up)
for (int j=node[i].rc;j!=i;j=node[j].rc)
{
node[node[j].up].down=j;
node[node[j].down].up=j;
cnt[node[j].col]++;
}
node[node[c].lc].rc=c;
node[node[c].rc].lc=c;
} void read_data()
{
for (int i=;i<=;i++)
for (int j=;j<=;j++)
{
char g;
scanf(" %c",&g);
map[i][j]=(int)g-'';
int c=id(i,j),t,k;
if (map[i][j])
{
k=map[i][j];
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
else
{
for (k=;k<=;k++)
{
t=(c-)*+k;
mx[t][c]=true;
mx[t][+*(i-)+k]=true;
mx[t][+*(j-)+k]=true;
mx[t][+(sqr[i][j]-)*+k]=true;
}
}
}
} void print()
{
for (int i=;i<=;i++)
{
for (int j=;j<=;j++)
printf("%d",ans[i][j]);
printf("\n");
}
} bool dfs(int step)
{
if (node[head].rc==head)
{
print();
return true;
} int i,j,c,t=,x,y,num,flag=;
for (i=node[head].rc;i!=head;i=node[i].rc)
if (cnt[i]<t)
{
t=cnt[i];
c=i;
}
if (t==)
return false;
cover(c); for (i=node[c].down;i!=c;i=node[i].down)
{
for (j=node[i].lc;j!=i;j=node[j].lc)
cover(node[j].col);
num=(node[i].row-)/+;
x=(num-)/+;
y=num-*(x-);
ans[x][y]=node[i].row-(num-)*;
if (dfs(step+))
return true;
for (j=node[i].rc;j!=i;j=node[j].rc)
uncover(node[j].col);
} uncover(c);
return false;
} void solve()
{
init(m);
build_link();
if (!dfs())
printf("-1\n");
} int main()
{
freopen("alone.in","r",stdin);
freopen("alone.out","w",stdout);
read_data();
solve();
return ;
}