舞蹈链 (DLX, Dancing Links X) 算法
精确覆盖问题
在一个全集X中若干子集的集合为S，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。
通俗地讲，给定一个 \(N\) 行 \(M\) 列的 01 矩阵。
你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 \(j\)，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。
X算法
这种算法可以看作搜索剪枝的最终版本，它可以解决 “精确覆盖问题”。
它的步骤如下：
- 任意在矩阵中选择一行，删除这一行、所有包含这一行中元素 \(1\) 的列以及包含这些列中 \(1\) 的元素的行。这一步可以看作搜索中的 “排除等效冗余”。
- 重复步骤1，直到矩阵为空。
- 第一种情况，我们上次选择的行中含有 \(0\)，说明仍有列未被覆盖，进行回溯。
- 第二种情况，我们上次选择的行中全是 \(1\)，说明得到了一组可行解。
- 如果回溯后无法选择，那么此问题无解。
模拟一遍：
\[\begin{pmatrix} 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 \end{pmatrix} \]选择第一行（红色代表被选中的行，蓝色代表被波及的列，绿色代表被波及的行）
\[\begin{pmatrix} \color{red} 0 & \color{red}0 & \color{red}1 & \color{red}0\\ \color{green} 1 & \color{green}0 & \color{blue}1 & \color{green}1\\ 0 & 0 & \color{blue}0 & 1\\ 0 & 1 & \color{blue}0 & 0\\ 1 & 1 & \color{blue}0 & 0 \end{pmatrix} \]删除
\[\begin{pmatrix} 0&0&1\\ 0 & 1 & 0\\ 1 & 1 & 0 \end{pmatrix} \]选择第一行
\[\begin{pmatrix} \color{red}0&\color{red}0&\color{red}1\\ 0 & 1 & \color{blue}0\\ 1 & 1 & \color{blue}0 \end{pmatrix} \]删除
\[\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \]选择第一行
\[\begin{pmatrix} \color{red}0 & \color{red}1\\ \color{green}1 & \color{blue}1 \end{pmatrix} \]删除后得到空矩阵，然而选择的行中含有 \(0\)，这不是一组可行解，进行回溯。
选择第二行
\[\begin{pmatrix} \color{green}0 & \color{blue}1\\ \color{red}1 & \color{red}1 \end{pmatrix} \]删除后得到空矩阵，并且选择的行中没有 \(0\)，得到一组可行解，可喜可贺，可喜可贺。
舞蹈链
观察发现，想要实现上述过程，需要一个精巧的数据结构支持高效的删除与恢复操作。
于是有了舞蹈链。
舞蹈链的本质就是 “双向十字链表”
双向链表我们都知道，链表内两个节点之间有左右指针互相连接，双向十字链表类似，只不过在原有的左右指针的基础上增加了上下两个指针，这样方便我们对矩阵进行操作。
初始化 build()
void build(int n) // 建舞蹈链，即建哨兵行
{
for (int i = 0; i <= n; i++) // 初始化哨兵
{
p[i].l = i - 1, p[i].r = i + 1;
p[i].col = i, p[i].row = 0;
p[i].up = p[i].down = i;
p[i].col_size = 0;
}
p[0].l = n, p[n].r = 0; // 哨兵行左右相连形成循环
memset(row_head, -1, sizeof row_head);
tot = n;
}
我们在舞蹈链内只记录对算法有本质影响的元素 \(1\)，舞蹈链支持三种修改操作，接下来一一讲解。
插入元素 insert()
void insert(int r, int c)
{
p[++tot].row = r, p[tot].col = c;
p[tot].up = p[c].up, p[tot].down = c; // 上下指针
p[p[tot].up].down = tot,
p[c].up = tot; // 对于哨兵行的操作
if (row_head[r] == -1) // 当前行没有节点，头指针就是当前节点
{
row_head[r] = tot;
p[tot].l = p[tot].r = tot;
}
else // 否则直接插入
{
p[tot].l = p[row_head[r]].l; // 左侧时当前行的末尾（头节点左侧）
p[tot].r = row_head[r]; // 右侧为头节点
p[p[tot].l].r = tot; // 原末尾节点左侧改成当前节点
p[p[tot].r].l = tot; // 头节点的左侧就是当前节点（因为末尾变了）
}
p[c].col_size++;
}
删除列 remove()
void remove(int c)
{
// 首先删除哨兵
p[p[c].l].r = p[c].r; // 左节点连到右节点
p[p[c].r].l = p[c].l; // 右节点连到左节点
for (int i = p[c].down; i != c; i = p[i].down) // 接着删除列元素
for (int j = p[i].r; j != i; j = p[j].r) // 把这一列全部删了
{
p[p[j].up].down = p[j].down; // 上节点连到下节点
p[p[j].down].up = p[j].up; // 下节点连到上节点
p[p[j].col].col_size--; // 对应列点数减少
}
}
恢复列 resume()
void resume(int c) // 删除操作的逆操作
{
p[p[c].l].r = p[p[c].r].l = c;
for (int i = p[c].down; i != c; i = p[i].down)
for (int j = p[i].r; j != i; j = p[j].r)
{
p[p[j].up].down = j;
p[p[j].down].up = j;
p[p[j].col].col_size++;
}
}
以上是舞蹈链支持的三种修改操作
X算法 dance()
这是通过舞蹈链实现的 X 算法。
bool dance(int u) // X算法
{
if (p[0].r == 0)
{
for (int i = 1; i < u; i++)
cout << ans[i] << ' ';
return true;
}
int t = p[0].r;
for (int i = p[0].r; i; i = p[i].r)
if (p[i].col_size < p[t].col_size)
t = i;
remove(t);
for (int i = p[t].down; i != t; i = p[i].down)
{
for (int j = p[i].r; j != i; j = p[j].r)
remove(p[j].col);
ans[u] = p[i].row;
if (dance(u + 1))
return true;
for (int j = p[i].r; j != i; j = p[j].r)
resume(p[j].col);
}
resume(t);
return false;
}
应用
很多问题也可以转换为 01矩阵覆盖问题，然后用 \(\text{DLX}\) 解决。
一般来说，我们把列作为题目中的约束限制，行作为可选的决策，每个决策满足一些约束，如果决策 \(i\) 满足约束 \(j\)，那么矩阵中 \((i, j)\) 的位置上就是 \(1\)，否则为 \(0\)。
数独
数独也可以转换为 01矩阵覆盖问题。
列
对于此题有四种约束：
- 第 \(i\) 行有数字 \(j\)。
- 第 \(i\) 列有数字 \(j\)。
- 第 \(i\) 宫内有 \(j\)。
最后一种是题目中隐含的约束，每个格子只能恰好放一个数字，因此最后一个约束是
- 格子 \((i, j)\) 填了数字。
以上每种约束有 \(256\) 种情况，因此 01矩阵 总共 \(4\times 256 = 1024\) 列。
行
每个格子放什么数字即为此题的决策：\((i, j)\) 放置数字 \(k\)，总共 \(16^3 = 4096\) 种决策，因此 01矩阵 总共 \(4096\) 行。
所以原数独问题转换成求解这个 \(4096 \times 1024\) 的01矩阵上的精准覆盖问题，可以用 \(\text{DLX}\) 解决。
参考代码
可以证明，原数独上的一组解等价于 01矩阵覆盖 的一组解。
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e4, M = 2e4, n = 16, ns = 256, m = 16 * 16 * 4;
char ch[20][20];
struct qaq
{
int x, y;
char type;
} rows[N];
struct qwq
{
int l, r, up, down; // 分别记录左右上下的点
int col_size; // 对于哨兵来说，当前列有多少点
int row, col; // 节点所在行/列
};
struct DLX
{
int idx, row_head[N], ans[N], top;
qwq p[N];
void build(int n) // 建舞蹈链，即建哨兵行
{
for (int i = 0; i <= n; i++) // 初始化哨兵
{
p[i].l = i - 1, p[i].r = i + 1;
p[i].col = i, p[i].row = 0;
p[i].up = p[i].down = i;
p[i].col_size = 0;
}
p[0].l = n, p[n].r = 0; // 哨兵行左右相连形成循环
memset(row_head, -1, sizeof row_head);
idx = n + 1;
}
// 接下来实现插入节点
void insert(int &hh, int &tt, int r, int c)
{
p[idx].row = r, p[idx].col = c, p[c].col_size++;
p[idx].up = c, p[idx].down = p[c].down, p[p[c].down].up = idx, p[c].down = idx;
p[hh].r = p[tt].l = idx, p[idx].r = tt, p[idx].l = hh;
tt = idx++;
}
// 接下来实现给定列的删除与恢复
void remove(int c)
{
// 首先删除哨兵
p[p[c].l].r = p[c].r, p[p[c].r].l = p[c].l; // 右节点连到左节点
for (int i = p[c].down; i != c; i = p[i].down) // 接着删除列元素
for (int j = p[i].r; j != i; j = p[j].r) // 把这一列全部删了
{
p[p[j].up].down = p[j].down; // 上节点连到下节点
p[p[j].down].up = p[j].up; // 下节点连到上节点
p[p[j].col].col_size--; // 对应列点数减少
}
}
void resume(int c) // 删除操作的逆操作
{
p[p[c].l].r = p[p[c].r].l = c;
for (int i = p[c].down; i != c; i = p[i].down)
for (int j = p[i].r; j != i; j = p[j].r)
{
p[p[j].up].down = j;
p[p[j].down].up = j;
p[p[j].col].col_size++;
}
}
bool dance() // X算法
{
if (!p[0].r)
{
for (int i = 1; i <= top; i++)
{
auto tmp = rows[ans[i]];
ch[tmp.x][tmp.y] = tmp.type;
}
for (int i = 0; i < 16; i++)
cout << ch[i] << endl;
cout << endl;
return true;
}
int t = p[0].r;
for (int i = p[0].r; i; i = p[i].r)
if (p[i].col_size < p[t].col_size)
t = i;
remove(t);
for (int i = p[t].down; i != t; i = p[i].down)
{
ans[++top] = p[i].row;
for (int j = p[i].r; j != i; j = p[j].r)
remove(p[j].col);
if (dance())
return true;
for (int j = p[i].l; j != i; j = p[j].l) // 改成 .r 会超时，原因未知 >_<
resume(p[j].col);
top --;
}
resume(t);
return false;
}
} dlx;
int main()
{
while (~scanf("%s", ch[0]))
{
for (int i = 1; i < 16; i++)
scanf("%s", ch[i]);
dlx.build(m);
for (int i = 0, tot = 1; i < 16; i++)
{
for (int j = 0; j < 16; j++)
{
int tmp1 = 0, tmp2 = 16 - 1;
if (ch[i][j] != '-')
tmp1 = tmp2 = ch[i][j] - 'A';
for (int k = tmp1; k <= tmp2; k++, tot++)
{
int hh = dlx.idx, tt = dlx.idx;
rows[tot] = {i, j, k + 'A'}; // 记录每行的具体内容，方便输出
dlx.insert(hh, tt, tot, i * 16 + j + 1); // 第四种约束
dlx.insert(hh, tt, tot, 256 + i * 16 + k + 1); // 行约束
dlx.insert(hh, tt, tot, 256 * 2 + j * 16 + k + 1); // 列约束
dlx.insert(hh, tt, tot, 256 * 3 + (i / 4 * 4 + j / 4) * 16 + k + 1); // 宫约束
}
}
}
dlx.dance();
}
return 0;
}