$Update\ 2022.8.5$:补充了 Dancing Links X 的算法解析,不会的同学可以看一看QAQ。
闲来无事,写篇题解。
这道题的Dancing Links X解法和上面那道数独,几乎一模一样,但上面那道题解太多了,所以就来这里写篇题解。
第一次在AcWing上写题解,本人语文菜的一批,见谅。
题目描述
填满 $16*16$ 的数独,保证解法唯一。
样例
略
本人比较菜,不会写DFS+剪枝,所以直接套一个Dancing Links X的模板。
数独属于NP完全问题,也就是说一定得用搜索做,DLX是一种比较优秀的搜索方式。
Dancing Links X:是一种用于解决精确覆盖的X问题(当然它也可以用于解决重复覆盖问题)。
精确覆盖问题举例:给出若干长度相等的 $01$ 串,取出若干条,使每个位置上恰有一个 $1$。
DLX的基本思路就是利用十字链表的数据结构,每次枚举选中的 $01$ 串,然后删除不可能的行以及已经无用的列,缩小规模继续搜索。具体代码实现指路模板,具体代码实现不给出,因为这里的空格太小,写不下。
数独是非常典型的可以用DLX解决的问题,这里着重介绍实现方法。
数独的约束条件是
- 每行恰有 $16$ 个不同的数;
- 每列恰有 $16$ 个不同的数;
- 每个宫每恰有 $16$ 个不同的数;
- 每个位置恰好有一个数。
其中第 $4$ 个条件是显而易见的,但是实现时容易遗漏。
用三元组 $(i,j,k)$ 表示在 $(i,j)$ 上的数是 $k$,对这个问题建模,每个可能的三元组构成 $01$ 矩阵的一行,每个约束条件构成 $01$ 矩阵的一列。
对于列,具体地说,有 $16*16=256$ 列记录数独每个数是否出现,$256$ 列记录数独 $16$ 行每行 $16$ 个数是否出现,$256$ 列记录数独 $16$ 列每列 $16$ 个数是否出现,$256$ 列记录数独 $16$ 宫 $16$ 个数是否出现,
一个完成的数独应当由 $16*16=256$ 个三元组表出,并且每个三元组满足四个约束条件。换句话说,目标是选出 $256$ 行,每行 $4$ 个 $1$,并且每列恰好 $1$ 个 $1$,这就转化成了 DLX 问题。
行的数量:$16 * 16 * 16=4096 $,列的数量:$16 * 16 * 4=1024$。只需枚举数独所有可能的情况,使用 DLX 算法判断是否可行。
一些细节
关于填数
枚举到 $(i,j,k)$,若当前是空格或者填的数恰好是 $k$,则可以尝试填上去。
if(!map[i][j] || map[i][j]==k)
节点插入的处理
* 每一个大的约束条件可以分裂成 $16*16=256$ 列。
* 每行相当于一个三元组,对三元组进行编号就是行的编号。
add(hd,tl,Row,(i-1)*16+j);
add(hd,tl,Row,256+(i-1)*16+k);
add(hd,tl,Row,256*2+(j-1)*16+k);
add(hd,tl,Row,256*3+((i-1)/4*4+(j-1)/4)*16+k);
输出处理
非常简单,记录答案的 $ans$ 数组中是行的编号,所以只需在插入是使用结构体数组对每行的编号做一个映射,求出 $ans$ 后再开数组映射回去就好了。
格式就是UVA格式,AcWing题面已经非常温馨地提示了要多打一个空行。
Code
Talk is easy, show me the code
#include<iostream>
#include<cstdio>
#include<cstring>
#define CI const int
using namespace std;
const int N=2e4+5,M=20;
int map[M][M],res[M][M];
int T,n,m,l[N],r[N],u[N],d[N];
int idx,ansn,s[N],row[N],col[N],ans[N];
char ch[20];
struct node
{
int x,y,v;
node(CI a,CI b,CI c):x(a),y(b),v(c){}
node(){}//构造函数
}p[N];
void clear()
{
ansn=0,n=4096,m=1024;
memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(u,0,sizeof(u));
memset(d,0,sizeof(d));
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(map,0,sizeof(map));
memset(res,0,sizeof(res));
memset(ans,0,sizeof(ans));//多组数据,我也懒得考虑清哪些数组,索性全清了
}
void init()
{
for(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;
idx=m+1;//起初每个节点全部指向自己
}
void add(int &hd,int &tl,int x,int y)
{
row[idx]=x,col[idx]=y,s[y]++;
u[idx]=y,d[idx]=d[y];
u[d[y]]=idx,d[y]=idx;
l[tl]=r[hd]=idx,l[idx]=hd,r[idx]=tl;
tl=idx++;//十字链表插入
}
void remove(int p)
{
l[r[p]]=l[p],r[l[p]]=r[p];
for(int i=d[p];i!=p;i=d[i])
for(int j=r[i];j!=i;j=r[j])
{
s[col[j]]--;
u[d[j]]=u[j],d[u[j]]=d[j];
}//。。。
}
void resume(int p)
{
for(int i=u[p];i!=p;i=u[i])
for(int j=l[i];j!=i;j=l[j])
{
u[d[j]]=j,d[u[j]]=j;
s[col[j]]++;
}
l[r[p]]=p,r[l[p]]=p;
//注意:要和remove执行相反操作才能把原数组回复
//也就是说remove的i按d删除,resume的i就必须按u恢复
}
bool dance()
{
if(!r[0]) return 1;
int p=r[0];
for(int i=r[0];i;i=r[i])
if(s[i]<s[p]) p=i;//找到最少1的列
remove(p);
for(int i=d[p];i!=p;i=d[i])
{
ans[++ansn]=row[i];//选中row[i]行
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);//删去无用的列
if(dance()) return 1;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
ansn--;
}
resume(p);
return 0;
}
void solve()
{
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
{
for(int k=1;k<=16;k++)
if(!map[i][j] || map[i][j]==k)
{
int hd=idx,tl=idx;
int Row=((i-1)*16+j-1)*16+k;
p[Row]=node(i,j,k);//映射
add(hd,tl,Row,(i-1)*16+j);
add(hd,tl,Row,256+(i-1)*16+k);
add(hd,tl,Row,256*2+(j-1)*16+k);
add(hd,tl,Row,256*3+((i-1)/4*4+(j-1)/4)*16+k);//每个三元组裂成4个节点插入
}
}
dance();//お前も舞うか(bushi
for(int i=1;i<=ansn;i++)
{
int rec=ans[i];
res[p[rec].x][p[rec].y]=p[rec].v;
}
for(int i=1;i<=16;i++,printf("\n"))
for(int j=1;j<=16;j++)
printf("%c",res[i][j]+'A'-1);
}
int main()
{
while(scanf("%s",ch+1)!=EOF)
{
clear(),init();
if(++T>1) printf("\n");
for(int i=1;i<=16;i++)
{
for(int j=1;j<=16;j++)
if(ch[j]=='-') map[i][j]=0;
else map[i][j]=ch[j]-'A'+1;
if(i!=16) scanf("%s",ch+1);
}
solve();
}
printf("\n");
return 0;
}
去注释版
#include<iostream>
#include<cstdio>
#include<cstring>
#define CI const int
using namespace std;
const int N=2e4+5,M=20;
int map[M][M],res[M][M];
int T,n,m,l[N],r[N],u[N],d[N];
int idx,ansn,s[N],row[N],col[N],ans[N];
char ch[20];
struct node
{
int x,y,v;
node(CI a,CI b,CI c):x(a),y(b),v(c){}
node(){}
}p[N];
void clear()
{
ansn=0,n=4096,m=1024;
memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(u,0,sizeof(u));
memset(d,0,sizeof(d));
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(map,0,sizeof(map));
memset(res,0,sizeof(res));
memset(ans,0,sizeof(ans));
}
void init()
{
for(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;
idx=m+1;
}
void add(int &hd,int &tl,int x,int y)
{
row[idx]=x,col[idx]=y,s[y]++;
u[idx]=y,d[idx]=d[y];
u[d[y]]=idx,d[y]=idx;
l[tl]=r[hd]=idx,l[idx]=hd,r[idx]=tl;
tl=idx++;
}
void remove(int p)
{
l[r[p]]=l[p],r[l[p]]=r[p];
for(int i=d[p];i!=p;i=d[i])
for(int j=r[i];j!=i;j=r[j])
{
s[col[j]]--;
u[d[j]]=u[j],d[u[j]]=d[j];
}
}
void resume(int p)
{
for(int i=u[p];i!=p;i=u[i])
for(int j=l[i];j!=i;j=l[j])
{
u[d[j]]=j,d[u[j]]=j;
s[col[j]]++;
}
l[r[p]]=p,r[l[p]]=p;
}
bool dance()
{
if(!r[0]) return 1;
int p=r[0];
for(int i=r[0];i;i=r[i])
if(s[i]<s[p]) p=i;
remove(p);
for(int i=d[p];i!=p;i=d[i])
{
ans[++ansn]=row[i];
for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
if(dance()) return 1;
for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
ansn--;
}
resume(p);
return 0;
}
void solve()
{
for(int i=1;i<=16;i++)
for(int j=1;j<=16;j++)
{
for(int k=1;k<=16;k++)
if(!map[i][j] || map[i][j]==k)
{
int hd=idx,tl=idx;
int Row=((i-1)*16+j-1)*16+k;
p[Row]=node(i,j,k);
add(hd,tl,Row,(i-1)*16+j);
add(hd,tl,Row,256+(i-1)*16+k);
add(hd,tl,Row,256*2+(j-1)*16+k);
add(hd,tl,Row,256*3+((i-1)/4*4+(j-1)/4)*16+k);
}
}
dance();
for(int i=1;i<=ansn;i++)
{
int rec=ans[i];
res[p[rec].x][p[rec].y]=p[rec].v;
}
for(int i=1;i<=16;i++,printf("\n"))
for(int j=1;j<=16;j++)
printf("%c",res[i][j]+'A'-1);
}
int main()
{
while(scanf("%s",ch+1)!=EOF)
{
clear(),init();
if(++T>1) printf("\n");
for(int i=1;i<=16;i++)
{
for(int j=1;j<=16;j++)
if(ch[j]=='-') map[i][j]=0;
else map[i][j]=ch[j]-'A'+1;
if(i!=16) scanf("%s",ch+1);
}
solve();
}
printf("\n");
return 0;
}
黑题这不轻轻松松。