N 皇后问题-位运算
N 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
国际象棋中皇后可以攻击同行、同列以及同对角线的棋子。因此，N 皇后问题要求找到一种布局，使得任意两个皇后都不能处于同一行、同一列或同一对角线上。
冲突条件详解
在解决 N 皇后问题时，我们需要判断当前位置是否与已经放置的皇后发生冲突。冲突主要分为三种情况：
- 列冲突：两个皇后位于同一列
- 主对角线冲突：两个皇后位于同一主对角线（从左上到右下）
- 副对角线冲突：两个皇后位于同一副对角线（从右上到左下）
冲突条件的数学表示
对于棋盘上的两个点 (i₁, j₁) 和 (i₂, j₂)：
- 列冲突：j₁ = j₂
- 主对角线冲突：i₁ - j₁ = i₂ - j₂
- 副对角线冲突：i₁ + j₁ = i₂ + j₂
这可以简化为一个统一的条件判断：两个皇后在同一条对角线上当且仅当 abs(j₁ - j₂) = abs(i₁ - i₂)
数组版本
数组版本通过直接检查每个已放置皇后的位置来判断冲突：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 100;
int n; // 皇后数量
int path[N]; // 第i行的皇后摆在了那一列
// 检查0~i-1行皇后是否与(i, j)皇后冲突
bool check(int i, int j) { // i, j为当前行和列
// 枚举前i行
for (int k = 0; k < i; k++) { // k 为之前皇后的编号
// 检查第k行皇后与当前(i, j)皇后是否冲突
// j == path[k] 检查列冲突
// abs(j - path[k]) == abs(i - k) 检查对角线冲突
if (j == path[k] || abs(j - path[k]) == abs(i - k)) {
return false;
}
}
return true;
}
int f1(int i, int n) { // i: 当前来到的行 0-base
// 递归结束条件
if (i == n) {
return 1;
}
int ans = 0; // 统计解的个数
// 枚举列
for (int j = 0; j < n; j++) {
// 检查是否有冲突的皇后
if (check(i, j)) {
path[i] = j;
ans += f1(i + 1, n);
}
}
return ans;
}
int totalNqueens(int n) { return f1(0, n); }
代码解析：
- 数组记录每一行皇后所在的列位置
j == path[k]检查列冲突abs(j - path[k]) == abs(i - k)检查对角线冲突，这个条件的含义是：- 当两个皇后的位置行差绝对值等于列差绝对值时，它们在同一条对角线上
- 比如位置
(1,2)和(3,4)，行差为|3-1|=2，列差为|4-2|=2，所以它们在同一条对角线上
位运算版本
位运算版本通过位操作优化冲突检查，提高算法效率：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int n; // 皇后数量
int col; // 用整数状态(位信息)表示是否放皇后
int left;
int right;
int f2(int limit, int col, int left,
int right) { // limit:限制为几皇后问题 col:之前皇后的列影响
// left:左对角线影响 right:右对角线影响
// 递归结束条件
if (col == limit) {
return 1;
}
int ban = col | left | right; // 禁止的列
int candidate = limit & (~ban); // 候选列(能够放皇后的位置)
int place = 0; // 放置的列
int ans = 0;
while (candidate) {
place = candidate & (-candidate); // 获取当前列(提取出最右侧的1)
candidate ^= place;
ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);
}
return ans;
}
int totalNQueens(int n) {
int limit = (1 << n) - 1;
return f2(limit, 0, 0, 0);
}
位运算优化原理：
col：记录已被占用的列（第 i 位为 1 表示第 i 列已被占用）left：记录会被之前皇后攻击的左对角线位置right：记录会被之前皇后攻击的右对角线位置limit：限制棋盘大小，n 位全为 1 的二进制数ban：禁止放置皇后的位置candidate：可以放置皇后的位置
两种方法对比
| 特性 | 数组版本 | 位运算版本 |
|---|---|---|
| 时间复杂度 | O(N!) | O(N!) |
| 空间复杂度 | O(N) | O(N) |
| 实现难度 | 简单 | 复杂 |
| 执行效率 | 一般 | 高 |
| 可读性 | 好 | 较差 |
数组版本更容易理解和实现，而位运算版本通过位操作减少了判断冲突的时间，在实际运行中效率更高。
