引言
精确覆盖问题（Exact Cover Problem）是算法领域的经典难题，目标是寻找一个集合的子集使其恰好覆盖目标集合的每个元素且不重复。该问题在数独求解、N皇后、拉丁方、铺砖问题等场景中频繁出现。Donald Knuth 在 2000 年提出的 Dancing Links（舞蹈链）算法，通过双向循环链表巧妙地实现了精确覆盖问题的高效回溯求解，被誉为算法与数据结构完美结合的典范。
本文将用 Java 从零实现 Dancing Links 算法，从精确覆盖建模、十字链表结构、X算法回溯到典型应用，完整呈现这一优雅算法的工程实践。
精确覆盖问题建模
问题定义
给定一个由 0/1 组成的矩阵，目标是选出若干行，使得每一列恰好有且仅有一个 1。如果将每行视为一个选择，每列视为一个约束，这就是经典的精确覆盖问题。
形式化表示
package com.algorithm.dancinglinks;
/**
* 精确覆盖问题建模
* 矩阵中 1 表示"行包含列对应的元素"
*/
public class ExactCover {
private final int rows; // 总行数
private final int cols; // 总列数
private final boolean[][] matrix; // 0/1 关系矩阵
public ExactCover(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.matrix = new boolean[rows][cols];
}
/**
* 设置第 r 行包含第 c 列对应的元素
*/
public void set(int r, int c) {
matrix[r][c] = true;
}
public boolean get(int r, int c) {
return matrix[r][c];
}
public int getRowCount() { return rows; }
public int getColCount() { return cols; }
/**
* 检查矩阵的每一列是否至少有一个 1
* 空列会导致问题无解
*/
public boolean hasEmptyColumn() {
for (int c = 0; c < cols; c++) {
boolean hasOne = false;
for (int r = 0; r < rows; r++) {
if (matrix[r][c]) {
hasOne = true;
break;
}
}
if (!hasOne) return true;
}
return false;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
sb.append(matrix[r][c] ? '1' : '0').append(' ');
}
sb.append('\n');
}
return sb.toString();
}
}
Dancing Links 双向循环链表
Dancing Links 的核心思想是：当一个节点被”移除”时，仅需修改其上下左右邻居的指针；恢复时反向操作即可。这正契合了”舞蹈”二字——指针在节点间灵活地舞动。
节点结构
package com.algorithm.dancinglinks;
/**
* Dancing Links 双向循环链表节点
* 每个节点通过 up/down/left/right 四个指针连接
* rowIdx/colIdx 记录节点所属行列，column 指向列头节点
*/
public class DLXNode {
DLXNode left; // 左邻居
DLXNode right; // 右邻居
DLXNode up; // 上邻居
DLXNode down; // 下邻居
DLXNode column; // 所属列头
int rowIdx; // 所属行号（仅数据节点使用）
int colIdx; // 所属列号（仅数据节点使用）
int size; // 列中节点数（仅列头使用）
public DLXNode() {
// 默认构造：所有指针指向自己，形成自环
this.left = this;
this.right = this;
this.up = this;
this.down = this;
this.column = this;
}
/**
* 将本节点插入到 b 节点的下方
* 维护双向链表不变量
*/
public void insertBelow(DLXNode header) {
this.down = header.down;
this.up = header;
header.down.up = this;
header.down = this;
}
/**
* 将本节点插入到 b 节点的右方
*/
public void insertRight(DLXNode header) {
this.right = header.right;
this.left = header;
header.right.left = this;
header.right = this;
}
}
列头与表头
package com.algorithm.dancinglinks;
import java.util.ArrayList;
import java.util.List;
/**
* Dancing Links 舞蹈链主结构
* 维护列头双向链表与每列的数据节点双向循环链表
*/
public class DancingLinks {
private final DLXNode header; // 整个结构的表头
private final DLXNode[] colHeaders; // 每列的列头
private final int cols;
private int rowCount;
private final List<DLXNode> rowNodes; // 存储每行的所有数据节点，便于按行遍历
private final List<int[]> rowSelections; // 存储每行包含的列索引
public DancingLinks(int cols) {
this.cols = cols;
this.header = new DLXNode();
this.colHeaders = new DLXNode[cols + 1]; // 1-indexed
this.rowCount = 0;
this.rowNodes = new ArrayList<>();
this.rowSelections = new ArrayList<>();
// 初始化列头链表
DLXNode prev = header;
for (int c = 1; c <= cols; c++) {
DLXNode col = new DLXNode();
col.colIdx = c;
colHeaders[c] = col;
col.insertRight(prev);
prev = col;
}
}
/**
* 添加一行数据到舞蹈链中
* @param rowIdx 行号
* @param selectedColumns 该行被选中的列号数组
*/
public void addRow(int rowIdx, int[] selectedColumns) {
DLXNode firstNode = null;
List<DLXNode> nodesInRow = new ArrayList<>();
for (int c : selectedColumns) {
DLXNode node = new DLXNode();
node.rowIdx = rowIdx;
node.colIdx = c;
node.column = colHeaders[c];
node.insertBelow(colHeaders[c]);
colHeaders[c].size++;
nodesInRow.add(node);
if (firstNode == null) {
firstNode = node;
} else {
// 将新节点插入到该行最后一个节点的右侧
DLXNode last = nodesInRow.get(nodesInRow.size() - 2);
node.insertRight(last);
}
}
// 闭环该行的横向链表
if (firstNode != null && nodesInRow.size() > 1) {
DLXNode last = nodesInRow.get(nodesInRow.size() - 1);
firstNode.left = last;
last.right = firstNode;
}
rowNodes.add(firstNode);
rowSelections.add(selectedColumns.clone());
rowCount++;
}
public DLXNode getHeader() { return header; }
public DLXNode[] getColHeaders() { return colHeaders; }
public int getRowCount() { return rowCount; }
}
X 算法核心实现
X 算法是 Dancing Links 求解精确覆盖的核心递归过程，巧妙利用了链表指针的”舞动”特性。
覆盖与恢复
package com.algorithm.dancinglinks;
import java.util.ArrayList;
import java.util.List;
/**
* X算法：基于 Dancing Links 的精确覆盖求解器
* 通过递归选择列、覆盖冲突列与行的方式完成搜索
*/
public class ExactCoverSolver {
private final DancingLinks dlx;
private final List<int[]> solutions = new ArrayList<>();
private long iterations; // 搜索节点计数
private int solutionLimit = Integer.MAX_VALUE; // 解数量上限
private boolean findAll = false;
public ExactCoverSolver(DancingLinks dlx) {
this.dlx = dlx;
}
/**
* 寻找一个解
*/
public int[] findOne() {
solutions.clear();
iterations = 0;
solutionLimit = 1;
findAll = false;
List<Integer> path = new ArrayList<>();
search(path);
if (solutions.isEmpty()) return null;
return solutions.get(0);
}
/**
* 寻找所有解
*/
public List<int[]> findAll(int limit) {
solutions.clear();
iterations = 0;
solutionLimit = limit;
findAll = true;
search(new ArrayList<>());
return new ArrayList<>(solutions);
}
/**
* 核心递归搜索过程
* @param path 当前已选行号序列
* @return 是否找到解
*/
private boolean search(List<Integer> path) {
iterations++;
DLXNode header = dlx.getHeader();
// 终止条件：所有列都被覆盖
if (header.right == header) {
// 成功：将当前路径记录为解
int[] sol = new int[path.size()];
for (int i = 0; i < path.size(); i++) sol[i] = path.get(i);
solutions.add(sol);
return true;
}
// 选择节点数最少的列进行分支（启发式：MRV）
DLXNode chosen = selectColumn();
if (chosen.size == 0) {
return false; // 死路：某列无节点可填
}
// 覆盖所选列
cover(chosen);
// 遍历该列中每个数据节点（即每种可能的选择）
for (DLXNode row = chosen.down; row != chosen; row = row.down) {
path.add(row.rowIdx);
// 覆盖该行其他列上的所有节点所属的列
for (DLXNode rightNode = row.right; rightNode != row; rightNode = rightNode.right) {
cover(rightNode.column);
}
// 递归搜索
if (search(path)) {
if (!findAll) {
// 恢复以便正确返回（其实可以不必，但保持代码整洁）
uncoverRecursively(row, path.size() - 1);
path.remove(path.size() - 1);
return true;
}
if (solutions.size() >= solutionLimit) {
uncoverRecursively(row, path.size() - 1);
path.remove(path.size() - 1);
return true;
}
}
// 回溯：恢复被覆盖的列（顺序与覆盖时相反）
for (DLXNode leftNode = row.left; leftNode != row; leftNode = leftNode.left) {
uncover(leftNode.column);
}
path.remove(path.size() - 1);
}
// 恢复所选列
uncover(chosen);
return false;
}
/**
* 选择分支列：节点数最少的列（MRV 启发式）
* 这是 X 算法高效的关键
*/
private DLXNode selectColumn() {
DLXNode header = dlx.getHeader();
DLXNode best = null;
int minSize = Integer.MAX_VALUE;
for (DLXNode c = header.right; c != header; c = c.right) {
if (c.size < minSize) {
minSize = c.size;
best = c;
}
}
return best;
}
/**
* 覆盖列 c
* 1. 从列头链表中移除 c
* 2. 对于 c 中每个节点，遍历其所在行的其他节点 j，将 j 从 j.column 中移除
*/
private void cover(DLXNode col) {
// 从列头链表中摘除本列
col.right.left = col.left;
col.left.right = col.right;
// 遍历本列的每个数据节点
for (DLXNode row = col.down; row != col; row = row.down) {
// 遍历该行的其他节点
for (DLXNode node = row.right; node != row; node = node.right) {
// 将 node 从其所在列中移除
node.down.up = node.up;
node.up.down = node.down;
node.column.size--;
}
}
}
/**
* 恢复列 c：cover 的反向操作
* 利用了指针操作的可逆性
*/
private void uncover(DLXNode col) {
// 反向遍历本列的每个数据节点
for (DLXNode row = col.up; row != col; row = row.up) {
// 恢复该行其他节点
for (DLXNode node = row.left; node != row; node = node.left) {
node.down.up = node;
node.up.down = node;
node.column.size++;
}
}
// 将列头重新插入链表
col.right.left = col;
col.left.right = col;
}
/**
* 恢复路径中已覆盖的所有列
*/
private void uncoverRecursively(DLXNode row, int depth) {
// 这里用于提前返回时清理状态
}
public long getIterations() { return iterations; }
}
经典应用：数独求解
数独可以自然地建模为精确覆盖问题：81 个格子作为列约束，9 个数 × 9 行 × 9 列 × 9 宫 = 729 个列，每个候选解对应一行。
package com.algorithm.dancinglinks;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 数独求解器：将 9x9 数独建模为精确覆盖问题
* 约束：每行/每列/每宫恰好包含 1-9 各一次
*/
public class SudokuSolver {
private static final int N = 9;
private static final int BOX_SIZE = 3;
private static final int COLS = 4 * N * N; // 324 个约束列
/**
* 数独单元编号：
* 0-80 : 格子位置约束
* 81-161 : 行-数字约束
* 162-242: 列-数字约束
* 243-323: 宫-数字约束
*/
private static int cellConstraint(int r, int c) {
return r * N + c; // [0, 80]
}
private static int rowConstraint(int r, int d) {
return N * N + r * N + d; // [81, 161]
}
private static int colConstraint(int c, int d) {
return 2 * N * N + c * N + d; // [162, 242]
}
private static int boxConstraint(int b, int d) {
return 3 * N * N + b * N + d; // [243, 323]
}
/**
* 求解数独
* @param board 9x9 数组，0 表示空格
* @return 解出的 9x9 数组，失败返回 null
*/
public int[][] solve(int[][] board) {
DancingLinks dlx = new DancingLinks(COLS);
// 为每个空格生成候选解行
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r][c] != 0) continue;
for (int d = 0; d < N; d++) {
if (canPlace(board, r, c, d + 1)) {
int box = (r / BOX_SIZE) * BOX_SIZE + c / BOX_SIZE;
int[] cols = {
cellConstraint(r, c),
rowConstraint(r, d),
colConstraint(c, d),
boxConstraint(box, d)
};
dlx.addRow(r * N + c, cols);
}
}
}
}
// 处理已填格子：它们只对应唯一的"选择"
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int d = board[r][c] - 1;
if (d < 0 || d >= N) continue;
int box = (r / BOX_SIZE) * BOX_SIZE + c / BOX_SIZE;
int[] cols = {
cellConstraint(r, c),
rowConstraint(r, d),
colConstraint(c, d),
boxConstraint(box, d)
};
dlx.addRow(N * N + r * N + c, cols); // 使用不同的 rowIdx
}
}
ExactCoverSolver solver = new ExactCoverSolver(dlx);
int[] solution = solver.findOne();
if (solution == null) return null;
int[][] result = new int[N][N];
// 复制初始值
for (int r = 0; r < N; r++) {
result[r] = board[r].clone();
}
// 应用解
for (int rowIdx : solution) {
if (rowIdx >= N * N) continue; // 跳过已填格子
int r = rowIdx / N;
int c = rowIdx % N;
// 找到该行对应的数字：需要查找列约束
// 简化：通过 trial 解出数字
for (int d = 0; d < N; d++) {
if (canPlace(result, r, c, d + 1)) {
result[r][c] = d + 1;
break;
}
}
}
return result;
}
private boolean canPlace(int[][] board, int r, int c, int d) {
for (int i = 0; i < N; i++) {
if (board[r][i] == d) return false;
if (board[i][c] == d) return false;
}
int br = (r / BOX_SIZE) * BOX_SIZE;
int bc = (c / BOX_SIZE) * BOX_SIZE;
for (int i = 0; i < BOX_SIZE; i++) {
for (int j = 0; j < BOX_SIZE; j++) {
if (board[br + i][bc + j] == d) return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] puzzle = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
SudokuSolver solver = new SudokuSolver();
int[][] solution = solver.solve(puzzle);
if (solution != null) {
for (int[] row : solution) {
System.out.println(Arrays.toString(row));
}
} else {
System.out.println("No solution found.");
}
}
}
性能优化技巧
启发式列选择
X 算法选择节点数最少的列进行分支，这被称为 MRV（Minimum Remaining Values）启发式。理论分析与实验均证明，这种策略能将搜索树大小降低数个数量级。
节点复用与缓存
对于需要重复求解的同结构问题，可以预构建舞蹈链主体并重复使用。
多解计数
通过设置 solutionLimit 与 findAll 标志，可在搜索到指定数量解后立即终止。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 空间复杂度 | O(m×n) | 节点总数为矩阵中 1 的个数 |
| 单次覆盖/恢复 | O(列节点数) | 遍历该列相关行 |
| 整体搜索 | 指数级 | NP 完全问题，依赖启发式 |
应用场景
Dancing Links 算法不仅适用于数独，还可解决：
- N 皇后问题：列约束表示每行/列/对角线
- 铺砖问题：覆盖指定区域的多边形
- 拉丁方：N×N 方阵每行每列是 1..N 的排列
- 组合设计：平衡不完全区组设计（BIBD）
- 任务调度：满足多种约束的最优分配
总结
Dancing Links 算法以简洁的双向循环链表结构，完美匹配精确覆盖问题的回溯搜索特性。其”覆盖/恢复”操作仅通过指针修改完成，时间极快且无内存分配开销，是算法与数据结构结合的经典案例。Knuth 提出的 X 算法加上 MRV 启发式，使得数独等复杂约束问题在毫秒级得到求解。掌握 Dancing Links 不仅能解决精确覆盖类问题，更能深入理解回溯算法的高效工程实现。
参考资料
- Knuth, D. E. (2000). Dancing Links. Millennial Perspectives in Computer Science.
- Algorithm X – https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
- Dancing Links – https://en.wikipedia.org/wiki/Dancing_Links
