跳转至

B31【模板】舞蹈链（DLX）精确覆盖问题_哔哩哔哩_bilibili

跳舞链

跳舞链是链表的一种高级变种

Day6 舞蹈链 - 浩熙的博客 - 洛谷博客

摘抄学习笔记 | DLX

精确覆盖问题

e.g. 给定一个01矩阵，求至少选多少行可以使得每一列**恰好（体现：精确）**有一个1

只适用于稀疏图。

存图

对于每一个1，建立一个十字链表节点（即有上下左右4个指针），并且列表在左右方向和上下方向分别是循环的。即的一个指向最后一个。

创建：逐行地创建十字链表。每一行每一列分别设置一个链头（标兵）

既然DLX是用来优化暴力的，那么我们先考虑暴力：dfs枚举所有方案后判断。

剪枝：

  • 每次选择1的个数最少的一列枚举选择哪一个1

  • 选择了某一列后应该删除这一列，因为这一列已经满足要求了。同时应该删除这一列中所有1所在的行，因为“精确”，这些行已经不能选了。

  • 选择了某一行后应该删除这一行中所有1所在的列，因为这写列已经满足要求了。

  • 在删除行/列时，我们删除其标兵即可。

大致框架（递归）还是**改-下-恢**

详解

变量

int n, m;
int l[N], r[N],u[N],d[N];//四个方向的指针
int row[N],col[N];//每个点所在的行/列
int s[N];//每一列的节点数量
int ans[N];//标记选择了哪些行
int idx,top;

初始化

void init(){//初始化第0行的列表头
    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;//节点分配cnt
}

寻址原理：我们预先分配m个节点作为每一列的表头。这样我们要遍历第i列时，从节点i往下即可。我们的十字链表是循环的，所以当再一次访问到i时就说明遍历完了。

添加节点

十字链表的插入操作。注意插入时的是逐行从左到右插入的。

void add(int &hh,int &tt,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;
    r[hh]=l[tt]=idx,r[idx]=tt,l[idx]=hh;
    tt=idx++;
}

dfs

这一部分很想是八皇后的dfs

void remove(int p){//删除第p列
    r[l[p]]=r[p];l[r[p]]=l[p];//首先对列表头继续修改
    for(int i=d[p];i!=p;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j],d[u[j]]=d[j];
            s[col[j]]--;
        }
    }

}

void resume(int p){//复原第p列
    for(int i=u[p];i!=p;i=u[i]){
        for(int j=l[i];j!=i;j=l[j]){
            u[d[j]]=d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[p]]=l[r[p]]=p;
}


bool dfs(){
    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最少的，还存在的那1列
    }
  //下面就是dfs搜索套路了

    remove(p);//删除第p列

    for(int i=d[p];i!=p;i=d[i]){//枚举选择那个1并且删除那个1所在的行
        ans[++top]=row[i];
        for(int j=r[i];j!=i;j=r[j]){
            remove(col[j]);
        }
        if(dfs())return 1;
        for(int j=l[i];j!=i;j=l[j]){
            resume(col[j]);
        }
        top--;
    }
    resume(p);//恢复第p列
    return 0;
}

代码

/*
Edit by Ntsc.
*/

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)

#define rd read()
#define ot write
#define nl putchar('\n')
inline int rd{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}
const int N = 2e4 + 5;
const int M = 1e5;
const int MOD = 998244353;
const int INF = 1e9+5;

int n, m, l[N], r[N],u[N],d[N];
int row[N],col[N],s[N];
int ans[N],idx,top;

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;//节点分配cnt
}

void add(int &hh,int &tt,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;
    r[hh]=l[tt]=idx,r[idx]=tt,l[idx]=hh;
    tt=idx++;
}

void remove(int p){
    r[l[p]]=r[p];l[r[p]]=l[p];
    for(int i=d[p];i!=p;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j],d[u[j]]=d[j];
            s[col[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]]=d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[p]]=l[r[p]]=p;
}


bool dfs(){
    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最少的，还存在的那1列
    }
    remove(p);//删除p列

    for(int i=d[p];i!=p;i=d[i]){//枚举选择那个1并且删除那个1所在的行
        ans[++top]=row[i];
        for(int j=r[i];j!=i;j=r[j]){
            remove(col[j]);
        }
        if(dfs())return 1;
        for(int j=l[i];j!=i;j=l[j]){
            resume(col[j]);
        }
        top--;
    }
    resume(p);//恢复p列
    return 0;
}
signed main(){
    n=rd,m=rd;

    init();
    for(int i=1;i<=n;i++){
        int hh=idx,tt=idx;
        for(int j=1;j<=m;j++){
            int x=rd;
            if(x)add(hh,tt,i,j);
        }
    }

    // cerr<<"OK";

    if(dfs()){
        for(int i=1;i<=top;i++){
            cout<<ans[i]<<' ';
        }
    }else cout<<"No Solution!";
}

重复覆盖问题

是一个NP问题，配合IDA*优化。不用。

例题 #1【模板】舞蹈链（DLX）

题目背景

本题是舞蹈链模板——精确覆盖问题

题目描述

给定一个 \(N\) 行 \(M\) 列的矩阵，矩阵中每个元素要么是 \(1\)，要么是 \(0\)。

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 \(j\)，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。

输入格式

第一行两个数 \(N,M\)。

接下来 \(N\) 行，每行 \(M\) 个数字 \(0\) 或 \(1\)，表示这个矩阵。

输出格式

一行输出若干个数表示答案，两个数之间用空格隔开，输出任一可行方案均可，顺序随意。

若无解，输出 No Solution!。

对于 \(100\%\) 的数据，\(N,M\leq 500\)，保证矩阵中 \(1\) 的数量不超过 \(5000\) 个。

例题 #2 数独

题目描述

数独是根据 \(9 \times 9\) 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 \(1 - 9\) ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

思路

我们考虑到DLX可用解决什么——精确覆盖问题。模板题是什么——填01矩阵。那么相比DLX也没有更丰富的功能了，那么我们考虑转化题意。

把约束条件转换为 01 矩阵的列

1 ，每一格只能填一个数

一共 81 格，转换为 81 列第 1 列表示（ 1 ， 1 ）填了一个数字

第 2 列表示（ 1 ， 2 ）填了一个数字

...

第 81 列表示（ 9 ， 9 ）填了一个数字

2 ，每一行每种数只能填一个

一共 9 行，每行填 9 个数字，转换为 81 列

第 81 + 1 列表示第 1 行填了数字 1

第 81 + 2 列表示第 1 行填了数字 2

第 81 + 81 列表示第 9 行填了数字 9

3 ，每一列每种数只能填一个

一共 9 列，每列填 9 个数字，转换为 81 列

第 162 + 1 列表示第 1 列填了数字 1

第 162 + 2 列表示第 1 列填了数字 2

第 162 + 81 列表示第 9 列填了数字 9

4 ，每一宫每种数只能填一个

一共 9 宫，每宫填 9 个数字，转换为81列、

第 243 + 1 列表示第 1 宫填了数字 1

第 243 + 2 列表示第 1 宫填了数字 2

第 243 + 81 列表示第 9 宫填了数字 9

一共开 324 列来保证每个约束条件．

把决策转换为 01 矩阵的行

1 ．对于填了数字的格子

e.g.（ 1 ， 3 ）中填了一个数字 8

转换为约束条件，即：

  • （ 1 ， 3 ）填了一个数字第 1 行填了一个数字 8

  • 第 3 列填了一个数字 8

  • 第 1 宫填了一个数字 8

对应 01 矩阵有 4 列，需要开 1 行

2 ．对于没填数字格子要枚举这个格子的填入情况．

  • （ 1 ， 1 ）中填入数字 1 ，对应 01 矩阵有 4 列是1

  • （ 1 ， 1 ）中填入数字 2 ，对应 01 矩阵有 4 列是1

  • ...

  • （ 1 ， 1 ）中填入数字 9 ，对应 01 矩阵有 4 列是1

枚举 9 种填入情况，需要开 9 行来记录

其他说明

  • 对于每一种填法，在前81列都会在对于格子有一个1表示当前格子已选。如果当前格子原先已经填了，那么只有一行的这列是1，否则就有9行。根据DLX优先找1数量最少的列，所以会优先处理这些已经填上的，于是就会把哪些和已经填上了的数字冲突的情况删去。

  • 为了方便统计答案，如果一个格子已经填了，我们在创建其1行时要额外创建8个空行来对齐映射。

/*
Edit by Ntsc.
*/

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)

#define rd read()
#define ot write
#define nl putchar('\n')
inline int rd{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}
const int N = 2e6 + 5;
const int M = 1e3 + 5;
const int MOD = 998244353;
const int INF = 1e9+5;

int n, m;
int l[N], r[N],u[N],d[N];//四个方向的指针
int row[N],col[N];//每个点所在的行/列
int s[N];//每一列的节点数量
int ans[N];//标记选择了哪些行
int idx,top;
int a[M][M];

void init(){//初始化第0行的列表头
    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;//节点分配cnt
}

void add(int &hh,int &tt,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;
    r[hh]=l[tt]=idx,r[idx]=tt,l[idx]=hh;
    tt=idx++;
}

void remove(int p){
    r[l[p]]=r[p];l[r[p]]=l[p];
    for(int i=d[p];i!=p;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j],d[u[j]]=d[j];
            s[col[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]]=d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[p]]=l[r[p]]=p;
}


bool dfs(){
    if(!r[0]){
        // cerr<<"N";  
        for(int i=1;i<=top;i++){
            int x=(ans[i]-1)/9/9;
            int y=(ans[i]-1)/9%9;
            int v=(ans[i])%9;
            if(!v)v=9;
            a[x][y]=v;
        }
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)cout<<a[i][j]<<' ';
            cout<<endl;
        }
        return 1;
    }
    int p=r[0];
    for(int i=r[0];i;i=r[i]){
        if(s[i]<s[p])p=i;//找到1最少的，还存在的那1列
    }
    remove(p);//删除p列

    for(int i=d[p];i!=p;i=d[i]){//枚举选择那个1并且删除那个1所在的行
        ans[++top]=row[i];
        for(int j=r[i];j!=i;j=r[j]){
            remove(col[j]);
        }
        if(dfs())return 1;
        for(int j=l[i];j!=i;j=l[j]){
            resume(col[j]);
        }
        top--;
    }
    resume(p);//恢复p列
    return 0;
}
signed main(){
    n=729,m=324;

    init();
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            a[i][j]=rd;
            for(int k=1;k<=9;k++){
                int hh=idx,tt=idx;//对于DLX的每一行都要初始化
                if((!a[i][j])||a[i][j]==k){
                    int r=i*81+j*9+k;
                    add(hh,tt,r,i*9+j+1);
                    add(hh,tt,r,81+i*9+k);
                    add(hh,tt,r,81*2+j*9+k);
                    add(hh,tt,r,81*3+(i/3*3+j/3)*9+k);
                }//else 留出空行
            }
        }
    }
    // cout<<endl;
    // cerr<<"OK";
    dfs();

    // if(dfs()){
    //  for(int i=1;i<=top;i++){
    //         cout<<ans[i]<<' ';
    //     }
    // }else cout<<"No Solution!";
}

例题 #4 [NOI2005] 智慧珠游戏

www.luogu.com.cn

题目描述（不全）

https://cdn.luogu.com.cn/upload/pic/13769.png

现给出一个盘件的初始布局，求一种可行的智慧珠摆放方案，使所有的零件 都能放进盘件中。

思路

和数独一样，把每一种情况都转换为行，每一个格子对应一列，并且使用其它列来保证其他的约束条件。

e.g. 以第i行为例

用1~55列（j列）表示第i行这种放法是否占用了第j个格子。

用后12列（j列）表示第i行这种放法使用的盘件为第j件。

主要麻烦在于初始化所有行，即所有情况。是个大模拟，故不写代码。

例题 #3 [NOIP2009 提高组] 靶形数独

题目背景

此为远古题，不保证存在可以通过任意符合要求的输入数据的程序。

题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 \(9\) 格宽且 \(9\) 格高的大九宫格中有 \(9\) 个 \(3\) 格宽且 \(3\) 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 \(1\) 到 \(9\) 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

https://cdn.luogu.com.cn/upload/image_hosting/dhvuc32i.png

上图具体的分值分布是：最里面一格（黄色区域）为 \(10\) 分，黄色区域外面的一圈（红色区域）每个格子为 \(9\) 分，再外面一圈（蓝色区域）每个格子为 \(8\) 分，蓝色区域外面一圈（棕色区域）每个格子为 \(7\) 分，最外面一圈（白色区域）每个格子为 \(6\) 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 \(2829\)。游戏规定，将以总分数的高低决出胜负。

https://cdn.luogu.com.cn/upload/image_hosting/yx82mmnc.png

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

思路

和上面数独那道题几乎差不多。这里要枚举所有情况然后取max而不是找到一种就return。

注意无解情况。

/*
Edit by Ntsc.
*/

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)

#define rd read()
#define ot write
#define nl putchar('\n')
inline int rd{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}
const int N = 2e6 + 5;
const int M = 1e3 + 5;
const int MOD = 998244353;
const int INF = 1e9+5;

int n, m;
int l[N], r[N],u[N],d[N];//四个方向的指针
int row[N],col[N];//每个点所在的行/列
int s[N];//每一列的节点数量
int ans[N];//标记选择了哪些行
int idx,top;
int a[M][M];
int w[M][M];
int aans;
bool able;

void init(){//初始化第0行的列表头
    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;//节点分配cnt
}

void add(int &hh,int &tt,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;
    r[hh]=l[tt]=idx,r[idx]=tt,l[idx]=hh;
    tt=idx++;
}

void remove(int p){
    r[l[p]]=r[p];l[r[p]]=l[p];
    for(int i=d[p];i!=p;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j],d[u[j]]=d[j];
            s[col[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]]=d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[p]]=l[r[p]]=p;
}


bool dfs(){
    if(!r[0]){
        // cerr<<"N";  
        for(int i=1;i<=top;i++){
            int x=(ans[i]-1)/9/9;
            int y=(ans[i]-1)/9%9;
            int v=(ans[i])%9;
            if(!v)v=9;
            a[x][y]=v;
        }
        int res=0;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)res+=w[i][j]*a[i][j];
        }
        aans=max(res,aans);
        able=1;
        return 1;
    }
    int p=r[0];
    for(int i=r[0];i;i=r[i]){
        if(s[i]<s[p])p=i;//找到1最少的，还存在的那1列
    }
    remove(p);//删除p列

    for(int i=d[p];i!=p;i=d[i]){//枚举选择那个1并且删除那个1所在的行
        ans[++top]=row[i];
        for(int j=r[i];j!=i;j=r[j]){
            remove(col[j]);
        }
        // if(dfs())return 1; 要枚举所有情况，所以这里不return了
        dfs();
        for(int j=l[i];j!=i;j=l[j]){
            resume(col[j]);
        }
        top--;
    }
    resume(p);//恢复p列
    return 0;
}

void prework(){
    for(int i=0;i<9;i++)for(int j=0;j<9;j++)w[i][j]=6;
    for(int i=1;i<8;i++)for(int j=1;j<8;j++)w[i][j]=7;
    for(int i=2;i<7;i++)for(int j=2;j<7;j++)w[i][j]=8;
    for(int i=3;i<6;i++)for(int j=3;j<6;j++)w[i][j]=9;
    for(int i=4;i<5;i++)for(int j=4;j<5;j++)w[i][j]=10;

}
signed main(){
    n=729,m=324;

    prework();

    init();
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            a[i][j]=rd;
            for(int k=1;k<=9;k++){
                int hh=idx,tt=idx;//对于DLX的每一行都要初始化
                if((!a[i][j])||a[i][j]==k){
                    int r=i*81+j*9+k;
                    add(hh,tt,r,i*9+j+1);
                    add(hh,tt,r,81+i*9+k);
                    add(hh,tt,r,81*2+j*9+k);
                    add(hh,tt,r,81*3+(i/3*3+j/3)*9+k);
                }//else 留出空行
            }
        }
    }
    // cerr<<"OK";
    dfs();
    if(!able)cout<<-1<<endl;
    else cout<<aans<<endl;

    // if(dfs()){
    //  for(int i=1;i<=top;i++){
    //         cout<<ans[i]<<' ';
    //     }
    // }else cout<<"No Solution!";
}

  • 对于 \(40\%\) 的数据，数独中非 \(0\) 数的个数不少于 \(30\)；

  • 对于 \(80\%\) 的数据，数独中非 \(0\) 数的个数不少于 \(26\)；

  • 对于 \(100\%\) 的数据，数独中非 \(0\) 数的个数不少于 \(24\)。

NOIP 2009 提高组 第三题

练习 #1 Sudoku 2

【题目描述】

在数独游戏中，给定一个大的 9 × 9 网格，分成了较小的 3 × 3 子网格。例如，

https://cdn.luogu.com.cn/upload/image_hosting/acjiq3ud.png

在给定网格中的一些数字后，你的目标是确定剩余的数字，使得数字 1 到 9 恰好出现在以下位置：(1) 九个 3 × 3 子网格中的每一个，(2) 九行中的每一个，以及 (3) 九列中的每一个。

【输入格式】

输入测试文件将包含多个案例。每个测试案例由一行组成，其中包含 81 个字符，这些字符代表数独网格的 81 个方格，逐行给出。每个字符可以是一个数字（从 1 到 9）或一个句点（用于表示未填充的方格）。你可以假设输入中的每个谜题都有唯一解。文件的结尾由一行包含单词“end”表示。

【输出格式】

对于每个测试案例，打印一行表示完成的数独谜题。

翻译来自于：ChatGPT

有些时候搜索+剪枝的复杂度可以DLX与相比。

Upd：好吧，DLX的常数是很优秀的，只不过：多测不清空，OIer两行泪。注意要把链表及其他数组全memset为0，init()只是用来初始化的，没有清空！

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
// #define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N=(1<<9);
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;



int row[11],col[11],mk[4][4],mp[N],ones[N];//每行，每列，每九宫格压缩后的状态
char s[100];

inline int lowbit(int x){return x&-x;}

int get(int x,int y){
    return row[x]&col[y]&mk[x/3][y/3];
}//计算出每个位置可填的数的个数
void init1(){
    int cnt=0;
    for(int i=0;i<N;i++){
        cnt=0;
        for(int j=i;j;j-=lowbit(j))cnt++;
        ones[i]=cnt;//预处理不同状态
    }
    for(int i=0;i<9;i++)mp[1<<i]=i;
}//预处理
void init2(){
    for(int i=0;i<9;i++)row[i]=col[i]=N-1;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)mk[i][j]=N-1;//多测要清空
}
bool dfs(int t){
    if(t==0)return 1;
    int mintp=10,x=0,y=0;
    for(int i=0,k=0;i<9;i++){
        for(int j=0;j<9;j++,k++){
            if(s[k]=='.'){
                int tp=ones[get(i,j)];
                if(tp<mintp)mintp=tp,x=i,y=j;//寻找可填数字最少的位置
            }
        }
    }
    for(int op=get(x,y);op;op-=lowbit(op)){
        int k=mp[lowbit(op)];//一次枚举可填的数字
        row[x]-=(1<<k),col[y]-=(1<<k),mk[x/3][y/3]-=(1<<k),s[x*9+y]=k+'1';//更新
        if(dfs(t-1))return 1;//搜索
        row[x]+=(1<<k),col[y]+=(1<<k),mk[x/3][y/3]+=(1<<k),s[x*9+y]='.';//还原现场
    }
    return 0;
}

void solve(){

    init1();
    while(scanf("%s",s)&&s[0]!='e'){
        init2();
        int num=0,k=0;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++,k++){
                if(s[k]=='.')num++;
                else{
                    int t=s[k]-'1';
                    row[i]-=(1<<t);
                    col[j]-=(1<<t);
                    mk[i/3][j/3]-=(1<<t);
                }
            }
        }
        dfs(num);
        printf("%s\n",s);
    }
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

练习 #2 Sudoku

题面翻译

给定一个\(16\times 16\)的数独，让你填好后输出（-为空格）

输入可能有多组数据（连续的几个16x16，中间没有空行，读到EOF为止）

输出格式：每次输出一组解后，跟一行空行。

PDF

只不过是将9x9变成了16x16罢了。

/*
Edit by Ntsc.
*/

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)

#define rd read()
#define ot write
#define nl putchar('\n')
inline int rd{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}
const int N = 2e5 + 5;
const int M = 5e3 + 5;
const int MOD = 998244353;
const int INF = 1e9+5;

int n, m;
int l[N], r[N],u[N],d[N];//四个方向的指针
int row[N],col[N];//每个点所在的行/列
int s[N];//每一列的节点数量
int ans[N];//标记选择了哪些行
int idx,top;
int a[M][M];

void init(){//初始化第0行的列表头

    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(s,0,sizeof s);
    memset(ans,0,sizeof ans);



    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;//节点分配cnt
}

void add(int &hh,int &tt,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;
    r[hh]=l[tt]=idx,r[idx]=tt,l[idx]=hh;
    tt=idx++;
}

void remove(int p){
    r[l[p]]=r[p];l[r[p]]=l[p];
    for(int i=d[p];i!=p;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j],d[u[j]]=d[j];
            s[col[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]]=d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[p]]=l[r[p]]=p;
}


bool dfs(){
    if(!r[0]){
        // cerr<<"N";  
        for(int i=1;i<=top;i++){
            int x=(ans[i]-1)/16/16;
            int y=(ans[i]-1)/16%16;
            int v=(ans[i])%16;
            if(!v)v=16;
            a[x][y]=v;
        }
        for(int i=0;i<16;i++){
            for(int j=0;j<16;j++)cout<<char(a[i][j]-1+'A');
            cout<<endl;
        }
        return 1;
    }
    int p=r[0];
    for(int i=r[0];i;i=r[i]){
        if(s[i]<s[p])p=i;//找到1最少的，还存在的那1列
    }
    remove(p);//删除p列

    for(int i=d[p];i!=p;i=d[i]){//枚举选择那个1并且删除那个1所在的行
        ans[++top]=row[i];
        for(int j=r[i];j!=i;j=r[j]){
            remove(col[j]);
        }
        if(dfs())return 1;
        for(int j=l[i];j!=i;j=l[j]){
            resume(col[j]);
        }
        top--;
    }
    resume(p);//恢复p列
    return 0;
}
char c[18];
signed main(){
    int cmr=0;
    n=4096,m=1024;

    while(1){
        init();
        for(int i=0;i<16;i++){
            if(scanf("%s",c)==EOF)exit(0);
            if(i==0&&cmr)puts("");
            for(int j=0;j<16;j++){

                a[i][j]=(c[j]=='-')?0:c[j]-'A'+1;
                for(int k=1;k<=16;k++){
                    int hh=idx,tt=idx;//对于DLX的每一行都要初始化
                    if((!a[i][j])||a[i][j]==k){
                        int r=i*256+j*16+k;
                        add(hh,tt,r,i*16+j+1);
                        add(hh,tt,r,256+i*16+k);
                        add(hh,tt,r,256*2+j*16+k);
                        add(hh,tt,r,256*3+(i/4*4+j/4)*16+k);
                    }//else 留出空行
                }
            }
        }
        // cout<<endl;
        // cerr<<"OK";
        dfs();
        cmr++;


    }


    // if(dfs()){
    //  for(int i=1;i<=top;i++){
    //         cout<<ans[i]<<' ';
    //     }
    // }else cout<<"No Solution!";
}