数独详解(剪枝与DLX)

· · 算法·理论

前言

本文由 chenhanzheapple 和 kexun_kevin 编写完成,其中第一部分由 kexun_kevin 编写完成。第二部分由 chenhanzheapple 编写完成。因此代码风格不同。

搜索

朴素 dfs

想要解决数独问题,我们不难想到可以在每个位置逐个 枚举所有数字,可以使用 dfs 算法。该算法并非本文主题,故仅附一份暴力代码供参考。

#include <iostream>
#include <cstring>
using namespace std;

int a[15][15];
bool r[15][15], c[15][15], g[15][15];

void print()
{
    for (int i = 1; i <= 9; ++i)
    {
        for (int j = 1; j <= 9; ++j)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}

bool chk()
{
    memset(r, false, sizeof r);
    memset(c, false, sizeof c);
    memset(g, false, sizeof g);
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= 9; ++j)
        {
            int x = a[i][j];
            if (r[i][x] || c[j][x] || g[(i-1)/3*3+(j-1)/3+1][x]) return false;
            r[i][x] = c[j][x] = g[(i-1)/3*3+(j-1)/3+1][x] = true;
        }
    return true;
}

void dfs(int x, int y)
{
    if (a[x][y])
    {
        if (x == 9 && y == 9)
        {
            if (chk())
            {
                print();
                exit(0);
            }
        }
        else if (y == 9) dfs(x+1, 1);
        else dfs(x, y+1);
        return;
    }
    for (int i = 1; i <= 9; ++i)
    {
        a[x][y] = i;
        if (x == 9 && y == 9)
        {
            if (chk())
            {
                print();
                exit(0);
            }
        }
        else if (y == 9) dfs(x+1, 1);
        else dfs(x, y+1);
        a[x][y] = 0;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= 9; ++j)
            cin >> a[i][j];
    dfs(1, 1);
    return 0;
}

可以发现该方法时间复杂度极高,所以必然不可行,因此需要剪枝。

剪枝

定义

剪枝是一种常见的搜索优化方式。

dfs 的搜索过程可呈现为一棵树,我们称之为 dfs 树,过程中每个选择都会对应其中的一个子树。

然而对一些选择后对最后结果一定没有任何价值的选项,我们自然而然地可以排除他们。具体的,我们应去除其对应子树,避免浪费时间。

可行性剪枝

可行性剪枝是最直观、基础的剪枝方式,具体来说就是去除掉不符合规则的选项。

在数独这个问题中,其具体表现如下:

\begin{pmatrix} 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 3 & 6 & 0 & 0 & 0 & 0 & 0\\ 0 & 7 & 0 & 0 & 9 & 0 & 2 & 0 & 0\\ 0 & 5 & 0 & 0 & 0 & 7 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 4 & 5 & 7 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 6 & 8\\ 0 & 0 & 8 & 5 & 0 & 0 & 0 & 1 & 0\\ 0 & 9 & 0 & 0 & 0 & 0 & 4 & 0 & 0 \end{pmatrix}

其中 0 表示未填数。

在该数独中,如果我们在 (1,2) 的位置填入数字 8 ,显然违反规则,所以该选项不用考虑。然而在上文所给代码中,该选项被试验了一遍,大大降低了效率,如果我们使用剪枝便可加快速度。

具体地,可以添加如下代码优化:

for (int i = 1; i <= 9; ++i)
{
   if (r[x][i] || c[y][i] || g[id[x][y]][i]) continue;
}

其中 r,c,g,id 分别为行、列、宫已选择数字和该位置对应宫号。

最优性剪枝

最优性剪枝也是一种较好理解的方式,具体为如果题目要求解最大、最小值等类型时,一旦目前所得数值大于已经求出的最优解,且后续数值离最优越来越远时,就可以停止搜索。

不过在数独问题中,我们无须利用此方法,故不做深入讲解。

重复性剪枝

这类剪枝的想法在于,如果你搜索到某一部分,发现这与之前已经计算过的某个方案完全等效,那我们就可以停止枚举,直接调用之前的结果。

不过这类剪枝在数独问题中也没有太大应用。

搜索顺序剪枝

这种方式就相对较抽象,利用了贪心思想。具体来说,我们如果有两个价值相等的部分,但其所需的尝试数量不同,我们应先解决次数较少的一个,因为其性价比更高。

不过这种方法在数独问题中其实更好理解,就是选择先枚举可填充数字最少的格子。计算机自然也可以实现类似功能。

实现

讲解了理论部分,下面就是实现部分。作者的代码主要运用了 可行性剪枝搜索顺序剪枝

不过由于想要找到目前可填数字最少的格子,暴力枚举是 O(9^3) 的,大大减慢了我们的速度。我们需用到 位运算 进行优化,优化过程不过多赘述。

#include <iostream>
#define lowbit(x) (x & -x)
using namespace std;

const int N = (1 << 9);
int n, a[10][10], cnt[N], f[N], r[10], c[10], g[10], cntn;
char ch;
int id[10][10] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                  {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
                  {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
                  {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
                  {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
                  {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
                  {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
                  {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
                  {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
                  {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}};

int get(int x)
{
    int cnt = 0;
    while (x)
    {
        ++cnt;
        x -= lowbit(x);
    }
    return cnt;
}

void qc(int x, int y, int num)
{
    r[x] ^= (1 << num);
    c[y] ^= (1 << num);
    g[id[x][y]] ^= (1 << num);
}

bool dfs(int cntn)
{
    if (!cntn) return true;
    int mn = 10, x, y, num;
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= 9; ++j)
            if (!a[i][j])
            {
                num = r[i] & c[j] & g[id[i][j]];
                if (cnt[num] < mn)
                {
                    x = i, y = j;
                    mn = cnt[num];
                }
            }
    num = r[x] & c[y] & g[id[x][y]];
    while (num)
    {
        int nw = f[lowbit(num)];
        a[x][y] = nw + 1;
        qc(x, y, nw);
        if (dfs(cntn - 1)) return true;
        a[x][y] = 0;
        qc(x, y, nw);
        num -= lowbit(num);
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i < N; ++i) cnt[i] = get(i);
    for (int i = 0; i <= 8; ++i) f[1<<i] = i;
    while (true)
    {
        cntn = 0;
        for (int i = 1; i <= 9; ++i) r[i] = c[i] = g[i] = N - 1;
        for (int i = 1; i <= 9; ++i)
            for (int j = 1; j <= 9; ++j)
            {
                cin >> ch;
                if (ch == 'e') return 0;
                if (ch == '.')
                {
                    a[i][j] = 0;
                    ++cntn;
                }
                else
                {
                    a[i][j] = ch - '0';
                    qc(i, j, a[i][j]-1);
                }
            }
        if (dfs(cntn))
            for (int i = 1; i <= 9; ++i)
                for (int j = 1; j <= 9; ++j)
                    cout << a[i][j];
        cout << '\n';
    }
    return 0;
}

使用 DLX 算法解决数独问题

引入——精确覆盖问题

定义

给定一个 nm 列的 01 矩阵,现在你需要挑选若干行,使得对于矩阵的每一列 j,在你挑选的这些行中,有且仅有一个 1。找到任意解。这个问题被称为精确覆盖问题。

例子

\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}

暴力

1

枚举每行是否被选择,时间复杂度 O(n \times m \times 2^n)

2

将每行看做一个二进制数,因此问题转换为:选择若干个二进制数,使它们的两两之间的按位与为 0,按位或为 2^n-1n 为选择二进制数的个数。枚举是否选择每个数,在搜索时判断即可做到 O(2^n)

正解

暴力不可行,因此需要使用一种新的算法——Dancing Links 优化 X 算法,简称 DLX 算法。

X 算法

定义-相关元素

x 行的所有元素打上标记,再将第 x 行中含 1 的列打上标记。所有打上标记的元素为 x 行的相关元素。

y 列的所有元素打上标记,再将第 y 列中含 1 的行打上标记。所有打上标记的元素为 y 列的相关元素。

定义-强相关元素

x 行的所有元素打上标记,将第 x 行中含 1 的列打上标记,再将上一步所有打上标记的列中含 1 的行打上标记。所有打上标记的元素为 x 行的强相关元素。

y 列的所有元素打上标记,将第 y 列中含 1 的行打上标记,再将上一步所有打上标记的行中含 1 的列打上标记。所有打上标记的元素为 y 列的强相关元素。

算法步骤

  1. 选择矩阵中未选择过的一行,设选中的这个行是 原来的x 行,将 x 加入到答案集合 S 中(这里我们统一按从第一行选择到最后一行选择)。如果所有行都已经尝试过,则判定为无解,算法结束。

  2. 删除所有 x 行的强相关元素。

  3. 若新矩阵为不为空,则转到第一步。若新矩阵为空且 x 行中的元素全部为 1,则找到答案,答案为需要选择集合 S 中的所有行。若新矩阵为空且之前选择的行中元素不是全部为 1,则转到第一步并将所有 x 的相关元素恢复。

例子

我们引用在精确覆盖问题中的例子来进行说明。

在这个例子中,我们先将这一行的所有强相关元素打上标记,再进行了删除操作。

初始矩阵为:

\begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}
  1. 选择第一行。红色为被选中行。

    \begin{pmatrix} \color{Red}0 & \color{Red}0 & \color{Red}1 & \color{Red}0 & \color{Red}1 & \color{Red}1 & \color{Red}0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}
  2. 将第一行的所有相关元素打上标记,其中蓝色表示标记。

    \begin{pmatrix} \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ 1 & 0 & \color{Blue}0 & 1 & \color{Blue}0 & \color{Blue}0 & 0 \\ 0 & 1 & \color{Blue}0 & 0 & \color{Blue}0 & \color{Blue}0 & 1 \\ \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}
  3. 删除所有被标记元素,得到一个新的小 01 矩阵:

    \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}
  4. 选择第一行(注意,这个第一行是新矩阵的第一行,下面所有对于行的称呼均为当前矩阵的行数)。

    \begin{pmatrix} \color{Red}1 & \color{Red}0 & \color{Red}1 & \color{Red}1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}
  5. 将第一行的所有相关元素打上标记。

    \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & \color{Blue}1 & \color{Blue}0 & \color{Blue}1 \end{pmatrix}
  6. 删除所有被标记元素,得到一个空矩阵。但是上次删除的行 1 0 1 1 不是全 1 的,说明选择有误,需要回到 这个例子的 第 4 步重新选择。

  7. 回溯到步骤 4,选择第二行。

    \begin{pmatrix} 1 & 0 & 1 & 1 \\ \color{Red}1 & \color{Red}0 & \color{Red}1 & \color{Red}0 \\ 0 & 1 & 0 & 1 \end{pmatrix}
  8. 将第二行的所有相关元素打上标记。

    \begin{pmatrix} \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}1 \\ \color{Blue}1 & \color{Blue}0 & \color{Blue}1 & \color{Blue}0 \\ \color{Blue}0 & 1 & \color{Blue}0 & 1 \end{pmatrix}
  9. 删除所有被标记元素,得到一个新的小 01 矩阵:

    \begin{pmatrix} 1 & 1 \end{pmatrix}
  10. 选择第一行。

    \begin{pmatrix} \color{Red}1 & \color{Red}1 \end{pmatrix}
  11. 将第二行的所有相关元素打上标记。

    \begin{pmatrix} \color{Blue}1 & \color{Blue}1 \end{pmatrix}
  12. 删除所有被标记元素,得到一个空矩阵,且上一次删除的时候,删除的是全 1 的行,算法结束,答案即为被选择的三行,即 S 中的编号:1, 4, 5

Dancing-Links 优化 X 算法(DLX 算法)

来源及基本思想

不难看出,X 算法需要大量的删除行、删除列和恢复行、恢复列的操作。

因此我们可以使用双十字链表维护。

而在双向十字链表上不断跳跃的过程被形象地比喻成跳跃,因此被用来优化 X 算法的双向十字链表也被称为 Dancing Links。

下文将介绍双十字链表的实现方式及 DLX 算法的实现方式。

时间复杂度

## 双十字链表(Dancing Links) ### 定义 双十字链表不同于普通链表,它有 $4$ 个指针,分别指向上、下、左、右四个元素。如下图所示是双十字链表里的单个节点。 以下所有关于指针数组的描述与下图相同。 ![](https://cdn.luogu.com.cn/upload/image_hosting/p76qrimu.png) 一整个双十字链表: ![](https://cdn.luogu.com.cn/upload/image_hosting/cg30g5mw.png) 其中 $first$ 数组指向的是每行的开头,而在每列的开头有一个哨兵节点(图中白色节点),红色的 $0$ 号节点是双十字链表的初始节点。 ### 操作 #### remove 操作 `remove(x)` 这个操作可以将第 $x$ 列的所有强相关元素移除。 注意:我们下文使用这个双十字链表时仅会插入为 $1$ 的位置,因此可以暴力删点。下同,不再赘述。 将第 $x$ 列移除仅需将其哨兵节点左右的节点连接即可。 接着枚举该列的所有结点,再枚举这些列所在的行,将这些行的所有节点的上下节点连接即可。 示例程序: ```cpp void remove(int x){ //第x行的哨兵节点即为x节点。 R[L[x]] = R[x]; L[R[x]] = L[x]; for(int y=U[x];y!=x;y=U[y]){ for(int z=R[y];z!=y;z=R[z]){//因为每行都是双向循环链表,因此可以从任意这一行的一点开始遍历。 U[D[z]] = U[z]; D[U[z]] = D[z]; sz[col[z]]--;//sz数组记录每列的元素个数,row_i表示i号元素属于哪一行,col_i表示i号元素属于哪一列,下同,并不再赘述。 } } } ``` #### recover 操作 `recover(x)` 这个操作可以将第 $x$ 列的所有强相关元素恢复。 这个操作即为 remove 操作的反向操作。 接着枚举该列的所有结点,再枚举这些列所在的行,将这些行的所有节点的上下节点连接到当前节点即可。 将第 $x$ 列移除仅需将其哨兵节点左右的节点连接到当前节点即可。 示例程序: ```cpp void recover(int x){ for(int y=U[x];y!=x;y=U[y]){ for(int z=R[y];z!=y;z=R[z]){ U[D[z]] = z; D[U[z]] = z; sz[col[z]]++; } } R[L[x]] = x; L[R[x]] = x; } ``` #### build 操作 `build(r,c)` 操作可以建一个新的长为 $r$,宽为 $c$ 的双十字链表。 我们仅需建出哨兵元素即可。 因为每一行都是双向循环链表,所以哨兵元素也不例外。 ![](https://cdn.luogu.com.cn/upload/image_hosting/gup99gc0.png) 示例程序: ```cpp void build(int r,int c){ n = r,m = c;//我们将双十字链表封装到结构体内,因此需要开设变量来保存边长。 for(int i=0;i<=c;i++){//建立哨兵节点 L[i] = i-1,R[i] = i+1; U[i] = i,D[i] = i;//因为双十字链表的每一列也是双向循环链表,因此初始哨兵节点的上、下指针均指向自己。 } L[0] = c; R[c] = 0; id = c+1;//id表示如果要添加元素的话,下一个元素的编号,下文阐述插入操作时将会使用。 } ``` #### insert 操作 `insert(r,c)` 操作能在第 $r$ 行,第 $c$ 列的位置插入一个节点(这个节点编号为 $id$,上文示例程序的注释中有提到,这里不再赘述,下同)。 先设置这个节点的行($row$ 数组)编号为 $r$,列($col$ 数组)编号为 $c$。 然后将节点 $id$ 插入到第 $c$ 行哨兵节点下方,即 $c$ 节点下方。**我们可以这样做是因为我们在删除与恢复操作时会遍历一整行或一整列,而每行或每列中元素顺序并不重要,下同,并不再赘述。** 之后我们分两种情况讨论。 - 若第 $r$ 行在插入之前没有节点,则直接将 $first_r$ 指向节点 $id$。$id$ 的左、右指针均为本身,即 $id$。 - 若第 $r$ 行在插入之前有节点,则将节点 $id$ 插入到 $first_r$ 之后。 示例程序: ```cpp void insert(int r,int c){ id++;//注意要改变下一次插入元素的编号 row[id] = r,col[id] = c; sz[c]++;//这里需要增加行元素个数 U[id] = c; D[id] = D[c]; U[D[c]] = id; D[c] = id; if(!first[r]){ first[r] = L[id] = R[id] = id; } else{ L[id] = first[r]; R[id] = R[first[r]]; L[R[first[r]]] = id; R[first[r]] = id; } } ``` #### dance 操作 `dance(x)` 操作能递归实现 X 算法,这个操作也是 DLX 算法的主体。 步骤如下: 1. 若 $0$ 号节点没有右节点,即矩阵(双十字链表)中没有任何元素时,算法结束,答案为 $S$ 中的所有元素。 2. 枚举所有列,找到 $sz$ 最小的列,即 $1$ 个数最少的列(**这里与上文介绍 X 算法流程的部分有不同,这是为了使程序有启发性,使递归次数更少,也就是速度更快**),使用 remove 操作删除它。 3. 枚举该列所有有 $1$ 的行,枚举其是否被选择。 4. 递归下去,如果找到答案,返回;如果无解,返回并报告无解;否则恢复该列。 示例程序: ```cpp bool dance(int x){ if(!R[0]){ ans = x; return 1; } int y = R[0]; for(int i=R[0];i;i=R[i]){ if(sz[i]<sz[y]){ y = i; } } remove(y); for(int i=D[y];i!=y;i=D[i]){ s[x] = row[i]; for(int j=R[i];j!=i;j=R[j]){ remove(col[j]); } if(dance(x+1)){ return 1; } for(int j=L[i];j!=i;j=L[j]){ recover(col[j]); } } recover(y); } ``` ### 最终程序/DLX 模板 ```cpp struct DLX{ int n,m,id,ans; int L[1005],R[1005],U[1005],D[1005],first[1005],sz[1005],row[1005],col[1005],s[1005]; void build(int r,int c){ n = r,m = c; for(int i=0;i<=m;i++){ L[i] = i-1,R[i] = i+1; U[i] = i,D[i] = i; } L[0] = c; R[c] = 0; id = c+1; } void remove(int x){ R[L[x]] = R[x]; L[R[x]] = L[x]; for(int y=U[x];y!=x;y=U[y]){ for(int z=R[y];z!=y;z=R[z]){ U[D[z]] = U[z]; D[U[z]] = D[z]; sz[col[z]]--; } } } void recover(int x){ for(int y=U[x];y!=x;y=U[y]){ for(int z=R[y];z!=y;z=R[z]){ U[D[z]] = z; D[U[z]] = z; sz[col[z]]++; } } R[L[x]] = x; L[R[x]] = x; } void insert(int r,int c){ row[id] = r,col[id] = c; sz[c]++; U[id] = c; D[id] = D[c]; U[D[c]] = id; D[c] = id; if(!first[r]){ first[r] = L[id] = R[id] = id; } else{ L[id] = first[r]; R[id] = R[first[r]]; L[R[first[r]]] = id; R[first[r]] = id; } id++; } bool dance(int x){ if(!R[0]){ ans = x; return 1; } int y = R[0]; for(int i=R[0];i;i=R[i]){ if(sz[i]<sz[y]){ y = i; } } remove(y); for(int i=D[y];i!=y;i=D[i]){ s[x] = row[i]; for(int j=R[i];j!=i;j=R[j]){ remove(col[j]); } if(dance(x+1)){ return 1; } for(int j=L[i];j!=i;j=L[j]){ recover(col[j]); } } recover(y); } }DancingLinks; ``` ## 建模 ### 基本思想 对于每道题,我们考虑行和列代表的意义。 行代表 **决策**,也就是选\不选。 列代表 **状态**,也就是约束条件。 对于某一行而言,由于不同的列的值不相同,我们 **由不同的状态,定义了一个决策**。 ## 解决数独问题 ### 决策-行 依照上文,因为有 $9$ 行 $9$ 列,每个格子可以填的数组有 $[1,9]$(离散状态下),因此DLX有 $9^3$ 行,即 $729$ 行。 ### 约束条件-列 在数独中,**每填一个数可以使用三元组 $(x,y,z)$ 表示,即在第 $x$ 行,第 $y$ 列填入了数 $z$。** 因此决策状态 $(x,y,z)$ 所造成的影响为: - 第 $x$ 行使用了数 $z$,这一行不能继续使用该数。 - 第 $y$ 列使用了数 $z$,这一列不能继续使用该数。 - 设第 $x$ 行第 $y$ 列所在的宫为第 $w$ 宫,则第 $w$ 宫使用了数 $z$,这一宫不能继续使用该数。 - 第 $x$ 行第 $y$ 列填入的数 $z$,这个位置不能再次填数。 因此决策有 $4$ 种影响,数独里有 $81$ 个格子,因此有 $81 \times 4$ 列,即 $324$ 列。有 $729 \times 4$ 即 $2916$ 个 $1$。 由于这一部分较难理解,同时较难说明,因此标程中不予注释。 ## 标程 ### 9×9 大小 例题:P10482 ```cpp #include<bits/stdc++.h> using namespace std; int a[15][15]; struct DLX{ int n,m,id,ans; int L[10005],R[10005],U[10005],D[10005],first[10005],sz[10005],row[10005],col[10005],s[10005]; void build(int r,int c){ memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); memset(U,0,sizeof(U)); memset(R,0,sizeof(R)); memset(first,0,sizeof(first)); memset(sz,0,sizeof(sz)); memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(s,0,sizeof(s)); n = r,m = c; for(int i=0;i<=m;i++){ L[i] = i-1,R[i] = i+1; U[i] = i,D[i] = i; } L[0] = c; R[c] = 0; id = c+1; } void remove(int x){ R[L[x]] = R[x]; L[R[x]] = L[x]; for(int i=D[x];i!=x;i=D[i]){ for(int j=R[i];j!=i;j=R[j]){ sz[col[j]]--; U[D[j]] = U[j]; D[U[j]] = D[j]; } } } void recover(int x){ for(int i=U[x];i!=x;i=U[i]){ for(int j=L[i];j!=i;j=L[j]){ D[U[j]] = U[D[j]] = j; sz[col[j]]++; } } R[L[x]] = L[R[x]] = x; } void insert(int r,int c){ id++; row[id] = r,col[id] = c; sz[c]++; U[id] = c; D[id] = D[c]; D[c] = U[D[c]] = id; if(!first[r]){ first[r] = L[id] = R[id] = id; } else{ L[id] = first[r]; R[id] = R[first[r]]; R[first[r]] = L[R[first[r]]] = id; } } bool dance(int x){ if(!R[0]){ for(int i=1;i<x;i++){ a[(s[i]-1)/81+1][(s[i]-1)/9%9+1] = (s[i]-1)%9+1; } return 1; } int y = R[0]; for(int i=R[0];i;i=R[i]){ if(sz[i]<sz[y]){ y = i; } } remove(y); for(int i=D[y];i!=y;i=D[i]){ s[x] = row[i]; for(int j=R[i];j!=i;j=R[j]){ remove(col[j]); } if(dance(x+1)){ return 1; } for(int j=L[i];j!=i;j=L[j]){ recover(col[j]); } } recover(y); return 0; } }DancingLinks; void work(int x,int y,int z){ int idx = (x-1)*81+(y-1)*9+z; DancingLinks.insert(idx,(x-1)*9+z); DancingLinks.insert(idx,(y-1)*9+z+81); DancingLinks.insert(idx,((x-1)/3*3+(y-1)/3)*9+z+162); DancingLinks.insert(idx,(x-1)*9+y+243); } int main(){ while(1){ DancingLinks.build(729,324); for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++){ char c; cin >> c; if(c=='e'){ return 0; } if(c>='0' && c<='9'){ a[i][j] = c-'0'; work(i,j,a[i][j]); } else{ for(int k=1;k<=9;k++){ work(i,j,k); } } } } DancingLinks.dance(1); for(int i=1;i<=9;i++){ for(int j=1;j<=9;j++){ cout << a[i][j]; } } cout << endl; } return 0; } ``` ### 16×16 大小 例题:UVA1309 基本思路与上文一致,仅需将计算行、列、宫时的公式换成 $16 \times 16$ 大小的公式,再将数组空间开大即可。 ```cpp #include<bits/stdc++.h> using namespace std; int a[105][105]; struct DLX{ int n,m,id,ans; int L[200005],R[200005],U[200005],D[200005],first[200005],sz[200005],row[200005],col[200005],s[200005]; void build(int r,int c){ memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); memset(U,0,sizeof(U)); memset(R,0,sizeof(R)); memset(first,0,sizeof(first)); memset(sz,0,sizeof(sz)); memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(s,0,sizeof(s)); n = r,m = c; for(int i=0;i<=m;i++){ L[i] = i-1,R[i] = i+1; U[i] = i,D[i] = i; } L[0] = c; R[c] = 0; id = c+1; } void remove(int x){ R[L[x]] = R[x]; L[R[x]] = L[x]; for(int i=D[x];i!=x;i=D[i]){ for(int j=R[i];j!=i;j=R[j]){ sz[col[j]]--; U[D[j]] = U[j]; D[U[j]] = D[j]; } } } void recover(int x){ for(int i=U[x];i!=x;i=U[i]){ for(int j=L[i];j!=i;j=L[j]){ D[U[j]] = U[D[j]] = j; sz[col[j]]++; } } R[L[x]] = L[R[x]] = x; } void insert(int r,int c){ id++; row[id] = r,col[id] = c; sz[c]++; U[id] = c; D[id] = D[c]; D[c] = U[D[c]] = id; if(!first[r]){ first[r] = L[id] = R[id] = id; } else{ L[id] = first[r]; R[id] = R[first[r]]; R[first[r]] = L[R[first[r]]] = id; } } bool dance(int x){ if(!R[0]){ for(int i=1;i<x;i++){ a[(s[i]-1)/256+1][(s[i]-1)/16%16+1] = (s[i]-1)%16+1; } return 1; } int y = R[0]; for(int i=R[0];i;i=R[i]){ if(sz[i]<sz[y]){ y = i; } } remove(y); for(int i=D[y];i!=y;i=D[i]){ s[x] = row[i]; for(int j=R[i];j!=i;j=R[j]){ remove(col[j]); } if(dance(x+1)){ return 1; } for(int j=L[i];j!=i;j=L[j]){ recover(col[j]); } } recover(y); return 0; } }DancingLinks; void work(int x,int y,int z){ int idx = (x-1)*256+(y-1)*16+z; DancingLinks.insert(idx,(x-1)*16+z); DancingLinks.insert(idx,(y-1)*16+z+256); DancingLinks.insert(idx,((x-1)/4*4+(y-1)/4)*16+z+512); DancingLinks.insert(idx,(x-1)*16+y+768); } int main(){ string s; int cnt = 0; while(cin >> s){ cnt++; if(cnt>1){ cout << endl; } DancingLinks.build(4096,1024); for(int i=1;i<=16;i++){ if(i!=1){ cin >> s; } for(int j=1;j<=16;j++){ char c = s[j-1]; if(c!='-'){ a[i][j] = c-'A'+1; work(i,j,a[i][j]); } else{ for(int k=1;k<=16;k++){ work(i,j,k); } } } } DancingLinks.dance(1); for(int i=1;i<=16;i++){ for(int j=1;j<=16;j++){ cout << (char)(a[i][j]+'A'-1); } cout << endl; } } return 0; } ```