数独详解（剪枝与DLX）

chenhanzheapple · 2025-01-17 10:20:02 · 算法·理论

前言

本文由 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 树，过程中每个选择都会对应其中的一个子树。

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

可行性剪枝

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

在数独这个问题中，其具体表现如下：

其中 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 算法解决数独问题

引入——精确覆盖问题

定义

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

例子

暴力

1

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

2

将每行看做一个二进制数，因此问题转换为：选择若干个二进制数，使它们的两两之间的按位与为 0，按位或为 2^n-1，n 为选择二进制数的个数。枚举是否选择每个数，在搜索时判断即可做到 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 的相关元素恢复。

例子

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

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

初始矩阵为：

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 算法的实现方式。

时间复杂度