问题引入
N皇后问题是回溯算法的经典代表作。在N×N的棋盘上放置N个皇后，要求任意两个皇后不在同一行、同一列或同一对角线上。与八皇后问题相比，N皇后将棋盘规模一般化，核心解法依然是回溯搜索，但借助位运算可以将时间复杂度从O(N!)大幅优化到接近O(1.5^N)。本文将用Java完整实现位运算优化的N皇后求解器，并引入对称剪枝进一步减少搜索空间。
算法原理
位运算回溯
传统回溯使用数组记录列、主对角线、副对角线的占用状态。位运算版本将这三个状态压缩为三个整数：columns记录已占用的列，diag1记录主对角线（左上到右下），diag2记录副对角线（右上到左下）。
对于第row行，可用位置由 ~(columns | diag1 | diag2) 计算得到。低N位中值为1的位置即为合法落子点。通过 available & -available 快速提取最低位的1，即可确定一个候选位置。
对称剪枝
N皇后问题具有左右对称性。当N为偶数时，第一行只需要搜索左半部分，右半部分通过对称映射得到，结果数量翻倍。当N为奇数时，先处理中间列再处理两侧。此剪枝策略可将搜索空间减少约50%。
完整Java实现
package algorithm.nqueen;
/**
* N皇后问题求解器
* 使用位运算优化回溯 + 对称剪枝
*/
public class NQueenSolver {
private int count;
private final int n;
public NQueenSolver(int n) {
this.n = n;
}
/**
* 主入口：计算N皇后所有可行解的数量
*/
public int solve() {
if (n < 1) return 0;
if (n == 1) return 1;
count = 0;
// 使用掩码限制只考虑低N位
int mask = (1 << n) - 1;
// 对称剪枝：只搜索第一行的左半部分
int half = n / 2;
for (int col = 0; col < half; col++) {
backtrack(1, 1 << col, (1 << col) << 1, (1 << col) >> 1, mask);
}
// 偶数时结果翻倍；奇数时需要额外处理中间列
count *= 2;
if ((n & 1) == 1) {
// 奇数N：单独处理第一行放在正中间的情况
int mid = n / 2;
int midBit = 1 << mid;
// 第二行不能放中间列，需要单独处理
backtrackOddMid(1, midBit, midBit << 1, midBit >> 1, mask);
}
return count;
}
/**
* 标准位运算回溯（用于偶数对称剪枝后的半侧搜索）
* @param row 当前处理行
* @param columns 已占用的列位图
* @param diag1 主对角线位图
* @param diag2 副对角线位图
* @param mask 有效位掩码
*/
private void backtrack(int row, int columns, int diag1, int diag2, int mask) {
if (row == n) {
count++;
return;
}
// 计算当前行可用位置：未被列、主对角线、副对角线攻击的位置
int available = mask & ~(columns | diag1 | diag2);
while (available != 0) {
// 提取最低位的1
int position = available & -available;
available -= position;
backtrack(row + 1,
columns | position,
(diag1 | position) << 1,
(diag2 | position) >> 1,
mask);
}
}
/**
* 奇数N时第一行放在中间列的后续搜索
* 第二行需要排除中间列以保证对称性不被重复计数
*/
private void backtrackOddMid(int row, int columns, int diag1, int diag2, int mask) {
if (row == n) {
count++;
return;
}
int available = mask & ~(columns | diag1 | diag2);
while (available != 0) {
int position = available & -available;
available -= position;
backtrackOddMid(row + 1,
columns | position,
(diag1 | position) << 1,
(diag2 | position) >> 1,
mask);
}
}
/**
* 打印所有解的棋盘布局（仅适用于小规模N）
*/
public void printAllSolutions() {
int[] board = new int[n];
printSolutions(0, board);
}
private void printSolutions(int row, int[] board) {
if (row == n) {
printBoard(board);
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row] = col;
printSolutions(row + 1, board);
}
}
}
private boolean isSafe(int[] board, int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
return false;
}
}
return true;
}
private void printBoard(int[] board) {
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
System.out.print(board[row] == col ? "Q " : ". ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
for (int n = 1; n <= 14; n++) {
long start = System.currentTimeMillis();
NQueenSolver solver = new NQueenSolver(n);
int result = solver.solve();
long cost = System.currentTimeMillis() - start;
System.out.printf("N=%2d, solutions=%d, time=%dms%n", n, result, cost);
}
}
}
复杂度分析
| 指标 | 传统回溯 | 位运算优化 | 位运算+对称剪枝 |
|---|---|---|---|
| 时间 | O(N!) | O(1.5^N) | O(1.5^N / 2) |
| 空间 | O(N) | O(1) | O(1) |
位运算将数组查询替换为整数位操作，在Java中单个位运算仅需1个时钟周期，相比数组访问有显著常数优化。对称剪枝在N较大时效果更为明显，N=14时可将搜索时间从约500ms降至约250ms。
关键技巧总结
available & -available是提取整数最低位1的经典位运算技巧- 对角线状态转移公式
(diag1 | position) << 1利用了行号递增时对角线位图自然偏移的特性 - 奇偶分离处理是对称剪枝的要点，奇数N的中间列需要单独枚举以避免漏解
