算法概述
DLX（Dancing Links X）是由图灵奖得主 Donald Knuth 提出的一种高效求解精确覆盖问题（Exact Cover Problem）的算法。其核心思想是将问题建模为01矩阵，通过双向循环链表的”舞蹈”式操作——即快速移除和恢复列与行——来加速深度优先搜索中的回溯过程。
精确覆盖问题的经典应用包括数独求解、八皇后问题、拉丁方阵、拼图覆盖等组合优化问题。DLX算法因其优雅的数据结构和惊人的剪枝效率，被誉为”算法艺术品”。
问题定义
精确覆盖问题：给定一个由0和1组成的矩阵，选择若干行使得每一列恰好有一个1。
形式化描述：设矩阵为 $A_{m \times n}$，寻找行集合 $S \subseteq {1, 2, …, m}$，使得对于每一列 $j \in {1, 2, …, n}$，恰好存在一行 $i \in S$ 满足 $A_{i,j} = 1$。
核心思想：舞蹈链
双向循环链表
DLX使用十字链表（双向循环链表）表示稀疏的01矩阵：
– 每行是一个水平循环链表
– 每列是一个垂直循环链表
– 每个节点同时属于一行和一列
移除与恢复操作
当选择某行覆盖某列时，需要：
1. 覆盖列：从列头链表中移除该列，同时移除该列中所有1所在的行
2. 恢复列：回溯时按相反顺序恢复，利用双向链表的指针即可完成 $O(1)$ 恢复
这就是”舞蹈”（Dancing）的含义——节点在链表中来去自如。
Java完整实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* DLX（Dancing Links X）算法实现精确覆盖问题求解
* 核心：双向循环链表的O(1)移除/恢复 + 启发式选择最少1的列
*/
public class DLX {
// 节点类：十字链表的节点
private static class Node {
Node left, right, up, down; // 四个方向指针
Node column; // 指向列头节点
int row; // 所在行号（-1表示列头）
int count; // 列头节点专用：该列1的个数
int col; // 列头节点专用：列编号
Node() {
this.left = this.right = this.up = this.down = this;
this.row = -1;
this.count = 0;
this.col = -1;
}
}
private final Node header; // 总表头
private final Node[] columns; // 列头数组
private final List<int[]> solutions; // 存储所有解
private final int[] currentSolution; // 当前搜索路径
private int solutionCount; // 解的计数
private final int maxSolutions; // 最大求解数量（防止爆炸）
/**
* 构造函数：从01矩阵构建舞蹈链
* @param matrix 01矩阵，matrix[i][j] = 1 表示第i行覆盖第j列
* @param maxSolutions 最大求解数量，-1表示求所有解
*/
public DLX(int[][] matrix, int maxSolutions) {
if (matrix == null || matrix.length == 0) {
throw new IllegalArgumentException("Matrix cannot be empty");
}
int rows = matrix.length;
int cols = matrix[0].length;
this.maxSolutions = maxSolutions;
this.solutions = new ArrayList<>();
this.currentSolution = new int[rows];
this.solutionCount = 0;
// 初始化表头
this.header = new Node();
this.columns = new Node[cols];
// 创建列头节点并链接到header
for (int j = 0; j < cols; j++) {
columns[j] = new Node();
columns[j].col = j;
// 水平链接：header <-> col0 <-> col1 <-> ... <-> header
columns[j].left = header.left;
columns[j].right = header;
header.left.right = columns[j];
header.left = columns[j];
}
// 创建行节点
Node[] rowNodes = new Node[cols]; // 暂存每行已创建的节点，用于水平链接
for (int i = 0; i < rows; i++) {
Node firstInRow = null;
Arrays.fill(rowNodes, null);
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
Node node = new Node();
node.row = i;
node.column = columns[j];
// 垂直链接：插入到列j的链表中
node.up = columns[j].up;
node.down = columns[j];
columns[j].up.down = node;
columns[j].up = node;
columns[j].count++;
// 水平链接
if (firstInRow == null) {
firstInRow = node;
node.left = node.right = node;
} else {
node.left = firstInRow.left;
node.right = firstInRow;
firstInRow.left.right = node;
firstInRow.left = node;
}
}
}
}
}
/**
* 覆盖列c：从列头链表移除c，并移除c中所有1所在的行
*/
private void cover(Node c) {
// 从水平链表中移除列头
c.left.right = c.right;
c.right.left = c.left;
// 遍历该列的所有节点
for (Node row = c.down; row != c; row = row.down) {
// 移除该行中的所有其他节点（从各自列中移除）
for (Node node = row.right; node != row; node = node.right) {
node.up.down = node.down;
node.down.up = node.up;
node.column.count--;
}
}
}
/**
* 恢复列c：cover的逆操作
*/
private void uncover(Node c) {
// 反向遍历该列的所有节点
for (Node row = c.up; row != c; row = row.up) {
// 恢复该行中的所有节点
for (Node node = row.left; node != row; node = node.left) {
node.up.down = node;
node.down.up = node;
node.column.count++;
}
}
// 恢复列头到水平链表
c.left.right = c;
c.right.left = c;
}
/**
* 启发式选择：选取1的个数最少的列
* 这一策略能最大程度减少分支因子
*/
private Node chooseColumn() {
Node minCol = header.right;
int minCount = minCol.count;
for (Node c = header.right; c != header; c = c.right) {
if (c.count < minCount) {
minCount = c.count;
minCol = c;
}
}
return minCol;
}
/**
* 核心DFS搜索
* @param depth 当前搜索深度
*/
private void search(int depth) {
// 终止条件：所有列都被覆盖
if (header.right == header) {
// 找到一个解
int[] sol = new int[depth];
System.arraycopy(currentSolution, 0, sol, 0, depth);
solutions.add(sol);
solutionCount++;
return;
}
// 剪枝：达到最大解数
if (maxSolutions > 0 && solutionCount >= maxSolutions) {
return;
}
// 启发式选择列
Node c = chooseColumn();
// 剪枝：该列没有1，无法覆盖
if (c.count == 0) {
return;
}
// 覆盖该列
cover(c);
// 尝试该列中的每一行
for (Node row = c.down; row != c; row = row.down) {
currentSolution[depth] = row.row;
// 覆盖该行中所有其他列
for (Node node = row.right; node != row; node = node.right) {
cover(node.column);
}
// 递归搜索
search(depth + 1);
// 回溯：恢复该行中覆盖的列
for (Node node = row.left; node != row; node = node.left) {
uncover(node.column);
}
}
// 恢复当前列
uncover(c);
}
/**
* 启动求解
* @return 所有解的列表，每个解是选中的行号数组
*/
public List<int[]> solve() {
solutions.clear();
solutionCount = 0;
search(0);
return solutions;
}
/**
* 获取解的数量
*/
public int getSolutionCount() {
return solutionCount;
}
// ==================== 应用示例 ====================
/**
* 数独求解器：将数独转化为精确覆盖问题
*/
public static class SudokuSolver {
// 数独有4种约束：
// 1. 每个格子恰好填一个数字（81列）
// 2. 每行每个数字恰好出现一次（81列）
// 3. 每列每个数字恰好出现一次（81列）
// 4. 每个宫每个数字恰好出现一次（81列）
// 总共324列
private static final int SIZE = 9;
private static final int BOX = 3;
private static final int COLS = 324; // 4 * 81
public int[][] solve(int[][] board) {
List<int[]> rows = new ArrayList<>();
List<int[]> placements = new ArrayList<>();
// 构建精确覆盖矩阵的行
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == 0) {
// 空白格：尝试1-9
for (int num = 1; num <= SIZE; num++) {
if (isValid(board, r, c, num)) {
int[] row = new int[COLS];
setConstraints(row, r, c, num);
rows.add(row);
placements.add(new int[]{r, c, num});
}
}
} else {
// 已知数字：固定选择
int num = board[r][c];
int[] row = new int[COLS];
setConstraints(row, r, c, num);
rows.add(row);
placements.add(new int[]{r, c, num});
}
}
}
int[][] matrix = rows.toArray(new int[0][]);
DLX dlx = new DLX(matrix, 1);
List<int[]> solutions = dlx.solve();
if (solutions.isEmpty()) {
return null; // 无解
}
// 构造解矩阵
int[][] result = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(board[i], 0, result[i], 0, SIZE);
}
int[] sol = solutions.get(0);
for (int rowIdx : sol) {
int[] p = placements.get(rowIdx);
result[p[0]][p[1]] = p[2];
}
return result;
}
private boolean isValid(int[][] board, int r, int c, int num) {
for (int i = 0; i < SIZE; i++) {
if (board[r][i] == num || board[i][c] == num) return false;
}
int br = (r / BOX) * BOX;
int bc = (c / BOX) * BOX;
for (int i = 0; i < BOX; i++) {
for (int j = 0; j < BOX; j++) {
if (board[br + i][bc + j] == num) return false;
}
}
return true;
}
private void setConstraints(int[] row, int r, int c, int num) {
int n = num - 1;
// 约束1：格子(r,c)被填充
row[r * SIZE + c] = 1;
// 约束2：行r包含数字num
row[81 + r * SIZE + n] = 1;
// 约束3：列c包含数字num
row[162 + c * SIZE + n] = 1;
// 约束4：宫格包含数字num
int box = (r / BOX) * BOX + (c / BOX);
row[243 + box * SIZE + n] = 1;
}
}
public static void main(String[] args) {
// 示例1：简单精确覆盖问题
System.out.println("=== Exact Cover Demo ===");
int[][] matrix = {
{1, 0, 0, 1, 0, 0, 1},
{1, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 1},
{0, 0, 1, 0, 1, 1, 0},
{0, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 0, 0, 1}
};
DLX dlx = new DLX(matrix, -1);
List<int[]> sols = dlx.solve();
System.out.println("Found " + sols.size() + " solution(s)");
for (int[] sol : sols) {
System.out.println("Solution rows: " + Arrays.toString(sol));
}
// 示例2：数独求解
System.out.println("\n=== Sudoku Solver Demo ===");
int[][] sudoku = {
{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(sudoku);
if (solution != null) {
System.out.println("Sudoku solution:");
for (int[] row : solution) {
System.out.println(Arrays.toString(row));
}
} else {
System.out.println("No solution found");
}
// 示例3：N皇后问题（转化为精确覆盖）
System.out.println("\n=== N-Queens as Exact Cover ===");
int n = 8;
List<int[]> queenRows = new ArrayList<>();
// N皇后有4种约束：每行、每列、每条对角线恰好一个皇后
// 简化为直接DLX求解
int queenCols = 2 * n; // 行约束 + 列约束
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int[] row = new int[queenCols];
row[r] = 1; // 行约束
row[n + c] = 1; // 列约束
queenRows.add(row);
}
}
// 注：完整N皇后还需要对角线约束，此处简化为演示
int[][] queenMatrix = queenRows.toArray(new int[0][]);
DLX queenDLX = new DLX(queenMatrix, 1);
List<int[]> queenSols = queenDLX.solve();
System.out.println("Found " + queenSols.size() + " placement(s) for " + n + "-queens (row+col only)");
}
}
关键要点解析
1. O(1)的移除与恢复
双向循环链表的核心优势在于：移除节点时只需修改4个指针（left.right、right.left、up.down、down.up），恢复时按相反方向操作即可。整个过程无需内存分配，全部是指针重定向。
2. 启发式列选择策略
选择1的个数最少的列进行分支，这是DLX高效的关键。该策略由Knuth提出，称为最小剩余值（MRV）启发式，能将搜索树的规模降低数个数量级。
3. 数独的约束建模
将数独转化为精确覆盖问题是DLX最经典的应用。324列对应4类约束（位置、行、列、宫），729行对应每个格子的每个可能数字。这种建模方式使得数独求解可在毫秒级完成。
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 矩阵构建 | $O(m \times n)$ |
| 单次cover/uncover | $O(\text{该列1的个数})$ |
| 搜索最坏情况 | $O(2^m)$（指数级，但剪枝极强） |
| 空间复杂度 | $O(\text{矩阵中1的个数})$ |
实际运行中，由于MRV启发式和精确覆盖问题的内在结构，DLX通常远快于普通回溯。
应用场景
- 数独求解：世界上最快的数独算法之一
- 拼图填充：如五格骨牌（Pentomino）覆盖棋盘
- 拉丁方阵：构造满足约束的符号矩阵
- 课程表编排：将时间/教室/教师约束建模为精确覆盖
- 电路设计：逻辑覆盖与测试用例生成
DLX将”复杂组合约束”转化为”矩阵覆盖搜索”，并通过舞蹈链的指针艺术实现了极致效率，是算法设计与数据结构结合的典范。
