推荐论文： momodi的《Dancing Links 在搜索中的应用》、Knuth的DLX论文、陈丹琦的《Dancing Links的应用》
Dancing Links是用来优化一类精确覆盖问题中的DFS过程。
精确覆盖问题是指在一个01矩阵中，选出一些行使每一列有且仅有1个1.
解法是Knuth提出的X算法：
1.矩阵被全部删除，搜索成功退出。
2.选择包含元素最少的一列c(可以随便选一列)删除，枚举这列含1的行r作为解的一部分，删除r行所有含1的列。
3.递归调用，成功返回，失败则回溯。
一般搜索中用bool数组标记行和列是否被删除，通过列找所有含1的行需要r次，通过行找所有的列需要c次，
然而在搜索过程中，矩阵的行和列不断被删除，不断减少，后面含1的行列很少，成为稀疏矩阵，
这时再使用r或c次的查找就是浪费时间了。
Dancing Links就是使用双向循环十字链表来存储矩阵，搜索过程中链表大小会不断减小，遍历一次就不需要r或c次了。
双向链表的删除操作：
L[R[x]] = L[x]; R[L[x]] = R[x];
双向链表的恢复操作也很简单：
L[R[x]] = x; R[L[x]] = x;
Knuth将支持这个操作的链表命名为Dancing Links 。
Sudoku 数独向精确覆盖问题的转换
数独有4个约束条件：
1.在i行只能放一个数字k
2.在j列只能放一个数字k
3.在block(i,j)块只能放一个数字k
4.i行j列只能放一个数字
所以建一个01矩阵：
行数n*n*n，n*n个格子，每个格子有n中可能，每种可能对应一行。
列数4*n*n，代表n*n个格子的4个约束条件。
如果数独i行j列已经有值k，则在(i*n+j)*n+k行插入4个1，列数分别是：
i*n+k-1
n*n+j*n+k-1
2*n*n+block(i,j)*n+k-1
3*n*n+i*n+j
否则插入n行，k=1 to n。
如果n=16，那么有4096行，1024列，矩阵遍历需要4096*1024=4194304次，
但是1的个数只有4096*4=16384个，Dancing Links 遍历只需要16384次。
这样对比下就可以看出Dancing Links 节约了很多时间。
调用DLX算法就可以求出数独的一个解或者判断无解。
n皇后问题也可以转换为精确覆盖问题。
还有一类重复覆盖问题：
在一个01矩阵中，选出一些行使每一列至少有1个1.
需要配合A*算法解决。
数独模板：
//POJ3076 736 KB 172 ms G++ 2689 B
#include<cstdio>
#define N 4099
#define M 1025
int m=4,n=m*m,H=4*n*n,cnt,size[M],ans[16][16];
struct Node
{
int r,c;
Node *U,*D,*L,*R;
}node[16385],row[N],col[M],head,*p;
void init(int r,int c)
{
cnt=0;
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;
col[i].R=head.R;
col[i].U=col[i].D=col[i].L->R=col[i].R->L=&col[i];
size[i]=0;
}
for(int i=r-1;i>=0;i--)
{
row[i].r=i;
row[i].c=c;
row[i].U=&head;
row[i].D=head.D;
row[i].L=row[i].R=row[i].U->D=row[i].D->U=&row[i];
}
}
void insert(int r,int c)
{
p=&node[cnt++];
p->r=r;
p->c=c;
p->R=&row[r];
p->L=row[r].L;
p->L->R=p->R->L=p;
p->U=&col[c];
p->D=col[c].D;
p->U->D=p->D->U=p;
++size[c];
}
void delLR(Node *p)
{
p->L->R=p->R;
p->R->L=p->L;
}
void delUD(Node *p)
{
p->U->D=p->D;
p->D->U=p->U;
}
void resumeLR(Node *p)
{p->L->R=p->R->L=p;}
void resumeUD(Node *p)
{p->U->D=p->D->U=p;}
void cover(int c)
{
if(c==H)
return;
delLR(&col[c]);
Node *R,*C;
for(C=col[c].D;C!=&col[c];C=C->D)
for(R=C->L;R!=C;R=R->L)
{
--size[R->c];
delUD(R);
}
}
void resume(int c)
{
if(c==H)
return;
Node *R,*C;
for(C=col[c].U;C!=&col[c];C=C->U)
for(R=C->R;R!=C;R=R->R)
{
++size[R->c];
resumeUD(R);
}
resumeLR(&col[c]);
}
int dfs(int k)
{
if(head.L==&head)
return 1;
int INF=-1u>>1,r,c=-1;
Node *p,*rc;
for(p=head.R;p!=&head;p=p->R)
if(size[p->c]<INF)
INF=size[c=p->c];
if(!size[c])
return 0;
cover(c);
for(p=col[c].D;p!=&col[c];p=p->D)
{
for(rc=p->L;rc!=p;rc=rc->L)
cover(rc->c);
r=p->r-1;
ans[r/(n*n)][r/n%n]=r%n;
if(dfs(k+1))
return 1;
for(rc=p->R;rc!=p;rc=rc->R)
resume(rc->c);
}
resume(c);
return 0;
}
void insert(int i,int j,int k)
{
int r=(i*n+j)*n+k;
insert(r,i*n+k-1);
insert(r,n*n+j*n+k-1);
insert(r,2*n*n+(i/m*m+j/m)*n+k-1);
insert(r,3*n*n+i*n+j);
}
char s[16][20];
void Sudoku()
{
int i,j,k;
init(n*n*n+1,H);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(s[i][j]!='-')
insert(i,j,k=s[i][j]-'A'+1);
else
{
for(k=1;k<=n;k++)
insert(i,j,k);
}
dfs(0);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
putchar(ans[i][j]+'A');
puts("");
}
puts("");
}
int main()
{
int i;
while(~scanf("%s",s[0]))
{
for(i=1;i<n;i++)
scanf("%s",s[i]);
Sudoku();
}
}
精确覆盖：
//01矩阵的完美覆盖 HUST1017
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
/***最大行***/
#define MAXROW 1005
/***最大列***/
#define MAXCOL 1005
int ans[MAXROW+5];
struct DancingLinksNode
{
int r, c; /***结点所在的行列位置***/
DancingLinksNode *U, *D, *L, *R;/***结点的上下左右结点指针***/
};
DancingLinksNode node[MAXROW * MAXCOL];/****备用结点****/
DancingLinksNode row[MAXROW];/****行头****/
DancingLinksNode col[MAXCOL];/****列头****/
DancingLinksNode head;/****表头****/
int cnt;/****使用了多少结点****/
int size[MAXCOL];/****列含有多少个域****/
int m, n;/****表的行与列变量****/
void init(int r, int c)/****初始化，r, c分别表示表的大小***/
{
cnt = 0;/****将可以使用的结点设为第一个****/
head.r = r; /****head结点的r,c分别表示表的大小,以备查****/
head.c = c;
head.L = head.R = head.U = head.D = &head;/****初始化head结点****/
for(int i = 0; i < c; ++i) /***初始化列头***/
{
col[i].r = r;
col[i].c = i;
col[i].L = &head;
col[i].R = head.R;
col[i].L->R = col[i].R->L = &col[i];
col[i].U = col[i].D = &col[i];
size[i] = 0;
}
for(int i = r - 1; i > -1; --i)/***初始化行头,在删除的时候，如果碰到row[i].c == c的情形应当被跳过***/
{
row[i].r = i;
row[i].c = c;
row[i].U = &head;
row[i].D = head.D;
row[i].U->D = row[i].D->U = &row[i];
row[i].L = row[i].R = &row[i];
}
}
inline void addNode(int r, int c)/****增加一个结点,在原表中的位置为r行,c列***/
{
DancingLinksNode *ptr = &node[cnt++];/****找一个未曾使用的结点****/
ptr->r = r;/****设置结点的行列号****/
ptr->c = c;
ptr->R = &row[r];/****将结点加入双向链表中****/
ptr->L = row[r].L;
ptr->L->R = ptr->R->L = ptr;
ptr->U = &col[c];
ptr->D = col[c].D;
ptr->U->D = ptr->D->U = ptr;
++size[c];/****将size域加1****/
}
inline void delLR(DancingLinksNode * ptr)/****删除ptr所指向的结点的左右方向****/
{
ptr->L->R = ptr->R;
ptr->R->L = ptr->L;
}
inline void delUD(DancingLinksNode * ptr)/****删除ptr所指向的结点的上下方向****/
{
ptr->U->D = ptr->D;
ptr->D->U = ptr->U;
}
inline void resumeLR(DancingLinksNode * ptr)/****重置ptr所指向的结点的左右方向****/
{
ptr->L->R = ptr->R->L = ptr;
}
inline void resumeUD(DancingLinksNode * ptr)/****重置ptr所指向的结点的上下方向****/
{
ptr->U->D = ptr->D->U = ptr;
}
inline void cover(int c)/****覆盖第c例***/
{
if(c == n)/**** 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);
}
}
inline void resume(int c)/****重置第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]);/****把列头接进表头中****/
}
bool search(int k)/****搜索核心算法,k表示搜索层数****/
{
if(head.L == (&head)) /***搜索成功,返回true***/
{
printf("%d\n",k);
for(int i=0;i<k;i++)
printf("%d\n",ans[i]);
return true;
}
/***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;
}
cover(c); /***覆盖第c列***/
DancingLinksNode * ptr;
for(ptr = col[c].D; ptr != (&col[c]); ptr = ptr->D)
{
DancingLinksNode *rc;
ptr->R->L = ptr;
for(rc = ptr->L; rc != ptr; rc = rc->L)
cover(rc->c);
ptr->R->L = ptr->L;
ans[k]=ptr->r+1;
if(search(k + 1))
return true;
ptr->L->R = ptr;
for(rc = ptr->R; rc != ptr; rc = rc->R)
resume(rc->c);
ptr->L->R = ptr->R;
}
resume(c);/***取消覆盖第c列***/
return false;
}
int main()
{
while(scanf("%d%d", &m, &n) != EOF)
{
init(m, n);
for(int i = 0; i < m; ++i)
{
int x,j;
scanf("%d",&x);
while(x--)
{
scanf("%d",&j);
j--;
addNode(i, j);//i行j列为1
}
}
if(!search(0))
puts("NO");
}
}
/*
模型的建立自然是要把冲突的条件都摆出来，这里有4个。
1.同行不能有相同的数
2.同列不能有相同的数
3.同块不能有相同的数
除了这3个很显然的约束，还有一个比较重要的，就是
4.每个位置只能有一个数
所以，对于一个9*9的数独，如此设置行:
(行标号，列标号)，(行标号，数)，(列标号，数)，(块标号，数)
每块都是9*9=81,一共是324个位置。
其中比据我要加入一个i行j列的数字k那么要加入一个含4个1的行，即
(i,j),(i,k),(j,k)(block(i,j),k)
block(i,j)返回(i,j)的块标号
如果有初始值的话把所有初始值都放一起，放在第0行，然后在第1层循环中做下特判，
只进行一次覆盖。。如果能保证第一次必然循环到此行就这么做。
否则，在递归开始前就先把这些列删除。提出前一种方案只是因为写起来方便。
*/