(\)
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 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]<s[y]) y=i; remove(y); for(R int i=d[y];i!=y;i=d[i]){ ans[t]=row[i]; for(R int j=r[i];j!=i;j=r[j]) remove(col[j]); if(dance(t+1)) return 1; for(R int j=l[i];j!=i;j=l[j]) restore(col[j]); } restore(y); return 0; } -
下面谈谈这种算法的优越性。
- 只记录(1)节点，节省了存储的空间。
- 每次选择(1)最少的列删除，保证了最优秀的搜索树形态，这已经做到了很多搜索时排序的任务。
- (Dancing Links)最优秀的地方在于，它删除是真实的，而直接用(bool)数组存储的方式，再删除时只能是对该行或该列打删除标记，具体做的时候只能时扫描到这一行再检验是否有标记，每次扫描复杂度都是整个矩阵的复杂度，而(Dancing Links)真实的删除能够大大降低扫描的时间。
(\)
Sudoku
-
数独问题是可以转化成精确覆盖问题的模型的，同理还有很多问题可以转换模型。
-
考虑标准的九宫数独，方案是每一个格子的九种方法，所以一共有(9 imes 9 imes 9=729)种答案集合，即实际的二维表最多有(729)行。
-
约束条件可以概括成下面四种：
- 每一行(1 ext~9)各出现一次
- 每一列(1 ext~9)各出现一次
- 每一宫(1 ext~9)各出现一次
- 每个位置上都出现数字
-
可以发现上面每个限制大小都是(9 imes 9=81)的，所以约束条件一共有(81 imes 4 =324)列。
-
我们需要一种合法的映射方式，使得可以快速的通过关键信息得到对应的行号和列号，并能够快速的还原，注意到每次都是在(9)的基础上产生的状态，并且都是三个关键字(()列的限制第一个关键字是四种类型())，我们可以采用(X imes 81+Y imes 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<cmath>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 750
#define M 350
#define S 247500
#define R register
#define gc getchar
using 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<int> 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]<s[y]) y=i;
remove(y);
for(R int i=d[y];i!=y;i=d[i]){
ans[t]=row[i];
for(R int j=r[i];j!=i;j=r[j]) remove(col[j]);
if(dance(t+1)) return 1;
for(R int j=l[i];j!=i;j=l[j]) restore(col[j]);
}
restore(y); return 0;
}
inline bool solve(){
res.clear();
if(!dance(0)) return 0;
for(R int i=0;i<anst;++i) res.push_back(ans[i]);
return 1;
}
}dlx;
int main(){
t=rd();
while(t--){
dlx.reset(maxr,maxc);
for(R int i=0;i<=8;++i)
for(R int j=0;j<=8;++j) num[i][j]=rd();
for(R int i=0;i<=8;++i)
for(R int j=0;j<=8;++j)
for(R int k=0;k<=8;++k)
if(num[i][j]==0||num[i][j]==k+1){
int x=calc(i,j,k);
dlx.insert(x,calc(0,i,j));
dlx.insert(x,calc(1,i,k));
dlx.insert(x,calc(2,j,k));
dlx.insert(x,calc(3,(i/3)*3+j/3,k));
}
dlx.solve(); int sz=res.size();
for(R int i=0,x,y,k;i<sz;++i){
restore(res[i],x,y,k); num[x][y]=k+1;
}
for(R int i=0;i<=8;++i){
for(R int j=0;j<=8;++j)printf("%d ",num[i][j]);
puts("");
}
}
return 0;
}