\(\\\)
Definitions
- 双向链表：记录前后两个指针的链表，每个顺序关系都有双向的指针维护。
- \(Dancing\ Links\)：双向十字循环链表，建立在二维关系上，每个元素记录上下左右四个指针，形成双向十字顺序关系，并且每行的尾元素的右指针指向该行头元素，每行的头元素的左指针指向该行尾元素，每列同样如此，形成了循环的结构。
- 精确覆盖问题：
- 已知全集元素和一些包含部分元素的子集，求出一个子集的集合，使得这个集合中的子集求并是全集，求交是空集。
- 已知所有的约束条件和一些满足部分约束的事件，求出一个事件集合，使得这些事件能够满足所有的约束条件，并且每一个约束条件只被这个集合中的一个事件满足。
- 形象化的说，给出一个\(01\)矩阵，选出矩阵中的几行，使得这几行构成的矩阵每列有且只有一个\(1\)。
- 解决精确覆盖问题的算法称为\(X\)算法，所以使用\(Dancing\ Links\)解决该问题的算法就称作\(Dancing\ Links\ X\)算法，是目前解决该问题的一种较快算法。
- 暴力的做法是，每层递归枚举选中的一行，扫描这一行所有\(1\)的位置对应的列，把该列上其他有\(1\)的行都删掉，递归下一层。合法的解出现当且仅当没有剩余的行的时候，所有的列都被覆盖过。这个思路非常重要，\(Dancing\ Links\ X\)算法其实是在模拟并优化这个过程。
\(\\\)
Dancing Links
- 普通的双向十字循环链表需要维护：
- \(U_X\)：编号为\(X\)的元素上方的第一个元素编号。
- \(D_X\)：编号为\(X\)的元素下方的第一个元素编号。
- \(L_X\)：编号为\(X\)的元素左侧的第一个元素编号。
- \(R_X\)：编号为\(X\)的元素右侧的第一个元素编号。
- \(Row_X\)：编号为\(X\)的元素所在行的编号。
- \(Col_X\)：编号为\(X\)的元素所在列的编号。
- \(Headrow_X\)：第\(X\)行的头元素编号。
- \(Headcol_X\)：第\(X\)列的头元素编号。
- 插入操作：
- 按从左上到右下的顺序扫描，插入一个坐标为\((X,Y)\)的\(1\)节点。
- 对于行和列操作是一样的，我们只讨论横向顺序关系。
- 查询\(Headrow_X\)是否存在：
- 若存在，根据循环链表的原则，当前节点的右指针指向\(Headrow_X\)，当前节点的左指针指向\(R_{Headrow_X}\)，注意也需要更新指向的两个节点的反向关系指针。
- 若不存在，则证明当前元素是该行的第一个元素，所以当前元素的左右指针都指向自己，并更新\(Headrow_X\)。
- 删除操作：
- 删除标号为\(X\)的节点。
- 注意到访问时指针的反向关系并不会影响到原顺序的访问，所以只删除当前节点所指向的四个节点指回这个节点的指针即可，不删除当前节点延伸出的指针，这样有助于后面的恢复操作。
- 恢复操作：
- 恢复编号为\(X\)的节点。
- 在本算法中，节点一般时计算前先建好，不需要内存回收，并且在搜索回溯的时候经常会用到恢复操作。
- 因为删除时并没有删掉当前节点延申的四个指针，所以可以直接访问到指向的四个元素，更改他们的指针反向指回到当前节点即可。
\(\\\)
可以发现这个算法所建立在的二维平面上，列是关键要素，每一列存在与否影响到答案的正确，而每一行的存在并没有约束条件。基于这个性质，在本算法中\(Dancing\ Links\)维护的信息有些更改：
- \(U_X\)：编号为\(X\)的元素上方的第一个元素编号。
- \(D_X\)：编号为\(X\)的元素下方的第一个元素编号。
- \(L_X\)：编号为\(X\)的元素左侧的第一个元素编号。
- \(R_X\)：编号为\(X\)的元素右侧的第一个元素编号。
- \(Row_X\)：编号为\(X\)的元素所在行的编号。
- \(Col_X\)：编号为\(X\)的元素所在列的编号。
- \(Head_X\)：第\(X\)行的头元素编号。
除掉上面这些，我们还需要维护：
- 每一列新建一个虚拟节点，代表列头，这个节点的有无就代表了这一列是否存在。
- 对于这些虚拟节点建立一个\(0\)元素，这个元素的右指针或左指针的有无决定了是否还存在待满足的约束。
\(S_X\)：第\(X\)列的元素个数，用于优化搜索的状态量。
- \(Ans\)：答案数组，记录选取的行编号。
\(tot\)：整个表内元素个数，用于建表。
下面系统的介绍整个数据结构的操作过程：
建表:
- 初始化第一行的虚拟节点，此时表中不存在真实元素，所以上下指针都指向每个虚拟元素自己，左右指针指向相邻的虚拟节点，注意\(0\)元素与最后一个元素是循环的。
- 注意要避免重复编号的情况，\(tot\)初始值应该是列数。
- 当多组数据时有必要重置\(S\)数组、\(Head\)数组、\(Ans\)数组。
inline void reset(int _n,int _m){ n=_n; m=tot=_m; memset(s,0,sizeof(s)); memset(h,-1,sizeof(h)); for(R int i=0;i<=m;++i){l[i]=i-1;r[i]=i+1;u[i]=d[i]=i;} l[0]=m; r[m]=0; }插入：
- 行处理还是与原来相同，列处理若该列为空则上下指针均指向列头的虚拟节点，注意更新\(tot\)和\(S\)。
inline void insert(int x,int y){ row[++tot]=x; col[tot]=y; ++s[y]; u[tot]=u[y]; d[tot]=y; d[u[tot]]=tot; u[d[tot]]=tot; if(h[x]==-1){h[x]=tot; l[tot]=tot; r[tot]=tot;} else{ l[tot]=l[h[x]]; r[tot]=h[x]; r[l[tot]]=tot; l[r[tot]]=tot; }}删除：
- 注意到我们删除操作是通过删除一列，进而删除这一列上的有\(1\)的行，所以用两个\(for\)循环解决。
- 发现一行是同时被删除的，恢复时也是同时被恢复的，所以只删除上下指针即可，左右指针无需删除。
- 代码传的参数时列编号，删除这一列上所有有\(1\)的行，注意维护列元素个数。
inline void remove(int y){ r[l[y]]=r[y]; l[r[y]]=l[y]; for(R int i=d[y];i!=y;i=d[i]) for(R int j=r[i];j!=i;j=r[j]){ u[d[j]]=u[j]; d[u[j]]=d[j]; --s[col[j]]; }}恢复：
- 操作基本与删除相同，将改后的指针改回来就好了，注意维护列元素个数。
inline void restore(int y){ for(R int i=d[y];i!=y;i=d[i]) for(R int j=r[i];j!=i;j=r[j]){ u[d[j]]=j; d[u[j]]=j; ++s[col[j]]; } r[l[y]]=y; l[r[y]]=y; }搜索\((Dance)\)：
- 模拟最开始做的思路即可，注意搜索树上层数越低的节点数对状态量的影响最大，所以我们应该尽可能减少搜索树上层数低的部分节点数，每次选择\(1\)最少的列进行搜索。
注意只删掉这一列还不够，要枚举这一列上选择那一行放入答案集合中，并删掉这一行上所有\(1\)所在的列，这里的删除是和上面相同的，也就是说，一次选择会导致很多列被删除。
传入的参数是当前递归的层数，便于记录答案。
bool dance(int t){ if(r[0]==0)return 1; int y=r[0]; for(R int i=r[0];i!=0;i=r[i]) if(s[i]
下面谈谈这种算法的优越性。
- 只记录\(1\)节点，节省了存储的空间。
- 每次选择\(1\)最少的列删除，保证了最优秀的搜索树形态，这已经做到了很多搜索时排序的任务。
- \(Dancing\ Links\)最优秀的地方在于，它删除是真实的，而直接用\(bool\)数组存储的方式，再删除时只能是对该行或该列打删除标记，具体做的时候只能时扫描到这一行再检验是否有标记，每次扫描复杂度都是整个矩阵的复杂度，而\(Dancing\ Links\)真实的删除能够大大降低扫描的时间。
\(\\\)
数独问题是可以转化成精确覆盖问题的模型的，同理还有很多问题可以转换模型。
考虑标准的九宫数独，方案是每一个格子的九种方法，所以一共有\(9\times 9\times 9=729\)种答案集合，即实际的二维表最多有\(729\)行。
约束条件可以概括成下面四种：
- 每一行\(1\text~9\)各出现一次
- 每一列\(1\text~9\)各出现一次
- 每一宫\(1\text~9\)各出现一次
- 每个位置上都出现数字
可以发现上面每个限制大小都是\(9\times 9=81\)的，所以约束条件一共有\(81\times 4 =324\)列。
我们需要一种合法的映射方式，使得可以快速的通过关键信息得到对应的行号和列号，并能够快速的还原，注意到每次都是在\(9\)的基础上产生的状态，并且都是三个关键字\((\)列的限制第一个关键字是四种类型\()\)，我们可以采用\(X\times 81+Y\times 9+Z\)的方式建立三个关键字的映射，并通过对\(9\)取余的一系列操作还原。
inline int calc(int x,int y,int k){return x*81+y*9+k+1;}inline void restore(int ans,int &x,int &y,int &k){ k=(--ans)%9; ans/=9; y=ans%9; x=(ans/9)%9;}注意记录答案，还原时找到位置注意更新数独。
#include#include #include #include #include #include #include #include #define N 750#define M 350#define S 247500#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}inline int calc(int x,int y,int k){return x*81+y*9+k+1;}inline void restore(int ans,int &x,int &y,int &k){ k=(--ans)%9; ans/=9; y=ans%9; x=(ans/9)%9;}vector res;int t,n,m,maxr=729,maxc=324,num[10][10];struct dlx{ int u[S],d[S],l[S],r[S],row[S],col[S]; int n,m,tot,anst,ans[N],s[M],h[N]; inline void reset(int _n,int _m){ n=_n; m=_m; for(R int i=0;i<=m;++i){l[i]=i-1; r[i]=i+1; u[i]=d[i]=i;} l[0]=m; r[m]=0; tot=m; memset(s,0,sizeof(s)); memset(h,-1,sizeof(h)); } inline void insert(int x,int y){ row[++tot]=x; col[tot]=y; ++s[y]; u[tot]=u[y]; d[tot]=y; d[u[tot]]=tot; u[d[tot]]=tot; if(h[x]==-1){h[x]=tot; l[tot]=tot; r[tot]=tot;} else{ l[tot]=l[h[x]]; r[tot]=h[x]; r[l[tot]]=tot; l[r[tot]]=tot; } } inline void remove(int y){ r[l[y]]=r[y]; l[r[y]]=l[y]; for(R int i=d[y];i!=y;i=d[i]) for(R int j=r[i];j!=i;j=r[j]){ u[d[j]]=u[j]; d[u[j]]=d[j]; --s[col[j]]; } } inline void restore(int y){ for(R int i=d[y];i!=y;i=d[i]) for(R int j=r[i];j!=i;j=r[j]){ u[d[j]]=j; d[u[j]]=j; ++s[col[j]]; } r[l[y]]=y; l[r[y]]=y; } bool dance(int t){ if(r[0]==0){anst=t;return 1;} int y=r[0]; for(R int i=r[0];i!=0;i=r[i]) if(s[i]