引言
八皇后问题要求在8×8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不能互相攻击。传统解法使用回溯法逐行尝试，而本文将展示一种更通用的数学建模思路——将问题转化为精确覆盖问题（Exact Cover Problem），并用Donald Knuth提出的Dancing Links（DLX）算法高效求解。这种方法不仅适用于八皇后，还能自然推广到N皇后、数独、拼图等组合问题。
核心算法原理
1. 精确覆盖问题建模
精确覆盖问题的定义：给定一个由0和1组成的矩阵，选择若干行，使得每一列恰好有一个1。
将八皇后问题建模为精确覆盖问题：
– 行：棋盘上每个可能的皇后位置，共64行。
– 列：约束条件，共8+8+15+15=32列：
– 8列：每行恰好一个皇后（Row约束）
– 8列：每列恰好一个皇后（Col约束）
– 15列：每条主对角线至多一个皇后（Diag约束）
– 15列：每条副对角线至多一个皇后（Anti-Diag约束）
对于位于 $(r, c)$ 的皇后，它在矩阵中对应的一行在第 $r$ 行约束列、第 $c$ 列约束列、第 $r+c$ 主对角线列、第 $r-c+7$ 副对角线列上为1。
2. Dancing Links算法
Dancing Links是Knuth提出的用于精确覆盖问题的深度优先搜索算法。其核心数据结构是一个双向循环链表构成的稀疏矩阵：
– 每列有一个列头节点，记录该列还有多少个1。
– 每个1对应一个节点，节点在水平方向构成行链表，在垂直方向构成列链表。
– 选择列头节点中计数最小的列（启发式策略），遍历该列的所有行，尝试将该行加入解集，同时从矩阵中删除所有冲突的行和列。
– 若搜索失败，则恢复（Dance back）被删除的节点，尝试下一行。
双向链表使得删除和恢复操作都只需要修改少量指针，因此称为”Dancing Links”。
Java实现
import java.util.*;
/**
* 八皇后问题 - Dancing Links精确覆盖求解
* 将N皇后建模为精确覆盖问题，使用DLX算法高效求解所有解
*/
public class NQueensDLX {
private int n; // 棋盘大小
private int solutions; // 解的计数
private List<int[]> allSolutions; // 存储所有解
// DLX节点
static class Node {
Node left, right, up, down;
ColumnHeader column;
int row; // 该行对应的棋盘位置索引
Node() {
left = right = up = down = this;
}
}
// 列头节点
static class ColumnHeader extends Node {
int size; // 该列中1的个数
int name; // 列名/编号
ColumnHeader(int name) {
this.name = name;
this.size = 0;
this.column = this;
}
}
private ColumnHeader header; // 总表头
private ColumnHeader[] columns; // 所有列头
private Node[] rows; // 每行的第一个节点（用于快速定位）
public NQueensDLX(int n) {
this.n = n;
this.solutions = 0;
this.allSolutions = new ArrayList<>();
buildMatrix();
}
/**
* 构建精确覆盖问题的稀疏矩阵（DLX链表结构）
* 列: 0~n-1 行约束, n~2n-1 列约束, 2n~3n-1 主对角线, 3n~4n-1 副对角线
*/
private void buildMatrix() {
int colCount = 4 * n;
columns = new ColumnHeader[colCount];
// 创建表头
header = new ColumnHeader(-1);
Node prev = header;
for (int i = 0; i < colCount; i++) {
columns[i] = new ColumnHeader(i);
// 将列头水平链接
prev.right = columns[i];
columns[i].left = prev;
prev = columns[i];
}
prev.right = header;
header.left = prev;
// 为棋盘上每个位置(r,c)创建一行
List<Node> rowNodes = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int diag = r + c; // 主对角线编号 0~2n-2
int antiDiag = r - c + n - 1; // 副对角线编号 0~2n-2
// 该位置对应的四个约束列
int[] colIndices = {r, n + c, 2 * n + diag, 3 * n + antiDiag};
Node firstNode = null;
Node prevNode = null;
for (int colIdx : colIndices) {
Node node = new Node();
node.row = r * n + c; // 该节点的行标识
node.column = columns[colIdx];
// 垂直方向链接到对应列
ColumnHeader col = columns[colIdx];
node.down = col;
node.up = col.up;
col.up.down = node;
col.up = node;
col.size++;
// 水平方向链接
if (firstNode == null) {
firstNode = node;
prevNode = node;
} else {
prevNode.right = node;
node.left = prevNode;
prevNode = node;
}
}
// 闭合水平循环链表
if (firstNode != null) {
prevNode.right = firstNode;
firstNode.left = prevNode;
}
rowNodes.add(firstNode);
}
}
rows = rowNodes.toArray(new Node[0]);
}
/**
* 覆盖某一列：从矩阵中删除该列及所有在该列有1的行
*/
private void cover(ColumnHeader col) {
// 从水平链表移除列头
col.right.left = col.left;
col.left.right = col.right;
// 遍历该列的每个节点
for (Node row = col.down; row != col; row = row.down) {
// 遍历该行的每个节点，从垂直链表移除
for (Node node = row.right; node != row; node = node.right) {
node.down.up = node.up;
node.up.down = node.down;
node.column.size--;
}
}
}
/**
* 恢复某一列：反向执行cover操作
*/
private void uncover(ColumnHeader col) {
// 从下到上恢复该列的每一行
for (Node row = col.up; row != col; row = row.up) {
// 从右到左恢复该行的每个节点
for (Node 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;
}
/**
* DLX深度优先搜索
*/
private void search(int depth, int[] currentSolution) {
// 终止条件：所有列都被覆盖
if (header.right == header) {
solutions++;
allSolutions.add(currentSolution.clone());
return;
}
// 启发式：选择1的个数最少的列（分支因子最小）
ColumnHeader minCol = null;
int minSize = Integer.MAX_VALUE;
for (ColumnHeader col = (ColumnHeader) header.right;
col != header; col = (ColumnHeader) col.right) {
if (col.size < minSize) {
minSize = col.size;
minCol = col;
if (minSize == 0) return; // 该列无法被覆盖，剪枝
if (minSize == 1) break;
}
}
if (minCol == null || minCol.size == 0) return;
// 覆盖选中的列
cover(minCol);
// 尝试该列中的每一行
for (Node row = minCol.down; row != minCol; row = row.down) {
// 记录当前选择的行（对应的棋盘位置）
currentSolution[depth] = row.row;
// 覆盖该行中所有其他列
for (Node node = row.right; node != row; node = node.right) {
cover(node.column);
}
// 递归搜索
search(depth + 1, currentSolution);
// 恢复该行覆盖的列
for (Node node = row.left; node != row; node = node.left) {
uncover(node.column);
}
}
// 恢复选中的列
uncover(minCol);
}
/**
* 求解并返回解的数量
*/
public int solve() {
solutions = 0;
allSolutions.clear();
search(0, new int[n]);
return solutions;
}
/**
* 打印指定解对应的棋盘
*/
public void printSolution(int[] sol) {
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
for (int pos : sol) {
int r = pos / n;
int c = pos % n;
board[r][c] = 'Q';
}
for (char[] row : board) {
for (char c : row) System.out.print(c + " ");
System.out.println();
}
System.out.println();
}
public List<int[]> getAllSolutions() {
return allSolutions;
}
public static void main(String[] args) {
// 求解八皇后问题
System.out.println("=== 八皇后问题 Dancing Links求解 ===\n");
NQueensDLX solver8 = new NQueensDLX(8);
int count8 = solver8.solve();
System.out.println("8皇后解的数量: " + count8);
// 打印前3个解
List<int[]> solutions8 = solver8.getAllSolutions();
for (int i = 0; i < Math.min(3, solutions8.size()); i++) {
System.out.println("解 " + (i + 1) + ":");
solver8.printSolution(solutions8.get(i));
}
// 对比不同规模
System.out.println("=== N皇后解的数量对比 ===");
for (int n = 1; n <= 12; n++) {
NQueensDLX solver = new NQueensDLX(n);
long start = System.currentTimeMillis();
int count = solver.solve();
long time = System.currentTimeMillis() - start;
System.out.printf("N=%2d: %6d 个解, 耗时 %3d ms%n", n, count, time);
}
}
}
复杂度分析
- 矩阵规模：N皇后问题的精确覆盖矩阵有 $N^2$ 行、$4N$ 列，每行恰有4个1。
- DLX搜索：最坏情况时间复杂度为指数级 $O(k^N)$，其中 $k$ 为平均分支因子。由于启发式选择最小列覆盖，实际运行效率远高于朴素回溯。
- 空间复杂度：$O(N^2)$ 个节点，每个节点存储4个指针，总空间 $O(N^2)$。
- 对比优势：传统回溯法需要 $O(N!)$ 的搜索空间，而DLX通过精确覆盖的约束传播和双向链表的O(1)删除恢复，在N=14以上时优势愈发明显。
扩展与应用
Dancing Links精确覆盖框架具有极强的通用性：
– 数独：将每个格子填入数字建模为行，行、列、宫、数字唯一性建模为列。
– 拼图填充：将每块拼图的每种放置方式建模为行，格子覆盖约束建模为列。
– 拉丁方、矩阵分解等组合问题均可套用最少的修改实现。
总结
本文将八皇后问题从传统的逐行回溯视角，转化为精确覆盖的数学框架，并通过Dancing Links算法高效求解。DLX的核心价值在于其通用性——同一套代码结构可以不加修改地应用于数独、拼图等众多组合问题。理解精确覆盖建模与双向链表的”舞蹈”机制，是掌握组合优化算法的重要一步。
