|
本文将介绍N皇后问题的五种解法，包括朴素回溯法、对称优化、标记优化、可用优化、位运算优化，对于每种解题思路，提供相应的非递归版代码实现，最后将对每种解法进行测试，横向对比每种解法的求解时间。
1. 题目描述
在 N×N 格的国际象棋上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
2. 回溯法
2.1 解题思路
回溯法是解决排列、组合、图着色以及约束满足问题等经典问题的通用方法之一，其核心思想是通过深度优先的搜索策略，在问题的解空间树中逐层探索所有可能的选择路径，并在发现当前选择不满足约束条件时及时“回退”，剪枝以避免无效计算。
对于 N 皇后问题而言，回溯法的基本做法是在棋盘上按行逐个尝试放置皇后，并在每一步判断当前列、主对角线、副对角线上是否已经存在冲突的皇后。如果当前位置合法，则继续进入下一行进行递归搜索；若当前位置不可行或后续子树无解，则回溯到上一步，尝试其他备选方案。
通常，回溯法可采用递归或非递归方式实现。递归形式因其表达简洁、语义直观，广泛用于入门教学与算法原型的构建。然而，递归方式往往隐藏了系统栈的调度细节，不利于统一比较不同优化策略在状态管理与栈空间控制方面的差异。因此，本文在所有算法实现中统一采用非递归版本，以显示搜索过程中的显式状态控制与剪枝策略，从而更清晰地揭示各类优化技术（如位压缩、对称规约）在回溯树结构中的嵌入方式。
2.2 代码实现
/**
* N皇后问题：回溯法（所有下标均从1开始）
* @param n 皇后的数量
* @return 摆法的数量
*/
int queen(int n) {
// 棋盘 当前放置哪个皇后 解的数量
int q[n + 1], k = 1, res = 0;
memset(q, 0, sizeof q);
// 判断第k个皇后放置位置是否合适
auto check = [&](int k) {
for (int i = 1; i < k; ++i)
// 同列、同斜线已存在皇后
if (q[i] == q[k] || abs(q[i] - q[k]) == abs(i - k))return false;
return true;
};
// 开始放置皇后
while (k > 0) {
// 第k个皇后尝试下一个位置
q[k]++;
// 寻找第k行的下一个可以放置的位置
while (q[k] <= n && !check(k))q[k]++;
// 已超过当前行的上限l，回溯，返回上一行
if (q[k] > n)--k;
// 如果放置完所有皇后，则记录结果，否则放置下一行
else k == n ? res++ : q[++k] = 0;
}
return res;
}
时间复杂度：O(n^{n^n})。
空间复杂度：O(n)。
3. 对称优化
3.1 解题思路
N 皇后问题本质上是一个在约束条件下的组合计数问题，其搜索空间随 N 的增加呈指数级增长。为了降低搜索复杂度，一种行之有效的策略是借助问题本身的几何对称性对解空间进行剪枝。具体而言，N 皇后问题的可行解天然存在于一个关于棋盘几何的对称群中。尽管完整的对称群包含水平翻转、垂直翻转、对角线翻转和旋转等七种组合关系，本文聚焦其中最直接也最具普适性的“左右对称”进行分析和剪枝。
在左右对称中，若存在一个可行解，其在第一行的皇后位于某一列 i，那么将该方案左右翻转（即将所有皇后在行内的位置变换为 n−i+1）后得到的也是一个合法解，且与原解互为镜像。去除重复方案后，剩下的刚好是N=5 时的全部方案，如图2 所示。
当 N 为偶数时关于中间那条线对称，当 N 为奇数时关于中间那一列对称。利用左右对称可以使得工作量减少一半，为了利用该对称性有效地减少运算量，我们对搜索过程施加如下两条限制：
-
第一行皇后的放置位置仅限于棋盘左半边，即列号小于等于 ⌊N/2⌋（用整数运算可写作 (N+1)/2）。
-
当 NNN 为奇数且第一行的皇后位于中间列时（即列号为 N+1/2），为了避免将该对称解计入两次，需要在第二行再施加对称性限制：第二行的皇后也仅能放在左边一半。
通过这样的限制，搜索过程中只保留对称类的一半代表解，最终将求得解数乘以 2（即 res << 1）即可还原完整的方案数。这种优化在 NNN 较大时能显著降低搜索深度与分支数。
3.2 代码实现
/**
* N皇后问题：对称优化（所有下标均从1开始）
* @param n 皇后的数量
* @return 摆法的数量
*/
int queen(int n) {
// 特判
if (n == 1)return 1;
// 棋盘 当前放置哪个皇后 解的数量
int q[n + 1], k = 1, res = 0;
memset(q, 0, sizeof q);
// 判断第k个皇后放置位置是否合适
auto check = [&](int k) {
for (int i = 1; i < k; ++i)
// 同列、同斜线已存在皇后
if (q[i] == q[k] || abs(q[i] - q[k]) == abs(i - k))return false;
return true;
};
// 中点位置 当前行最多能放到第几列
int m = (n + 1) >> 1, l;
// n是否为奇数
bool odd = n & 1;
// 开始放置皇后
while (k > 0) {
// 第k个皇后尝试下一个位置
q[k]++;
// 第一行放置的皇后不能超过中点
if (k == 1)l = m;
// n为奇数且第一行放在中间时，第二行不能超过中间
else if (k == 2 && odd && q[1] == m)l = m - 1;
// 其它情况可以放到中点右边
else l = n;
// 寻找第k行的下一个可以放置的位置
while (q[k] <= l && !check(k))q[k]++;
// 已超过当前行的上限l，回溯，返回上一行
if (q[k] > l)--k;
// 如果放置完所有皇后，则记录结果，否则放置下一行
else k == n ? res++ : q[++k] = 0;
}
return res << 1;
}
时间复杂度：O(n^{n^n})。
空间复杂度：O(n)。
4. 标记优化
4.1 解题思路
对于棋盘单元坐标，有如下规律（图 2 为两个 4×4 的棋盘）：
(1)同一正斜线所占据的单元的横纵坐标之和相等。
(2) 同一反斜线所占据的单元的横纵坐标之差相等。
由此，可以设置数组 L 和 R，表示斜线的占有情况，从而可以做到快速判断某位置是否可以放置皇后。
① L[i] 表示和为i 的正斜线是否被占据，i 的范围为[2,2N] ，故0,1两个位置舍去不用。
② R[i] 表示差为 i 的反斜线是否被占据，i 的范围为 [1-N,N-1]，为避免负下标，对 i 作加 N 处理。
L[i]中的i舍去0,1 两个位置，R[i] 中的 i 加 N 而不是加 N-1，都是为了减少计算量。
同时，再设置数组 Y，Y[i] 表示第 i 列是否被占据，1≤i≤N。改用根据数组 L,R,Y 来判断某位置是否可以放置皇后，可减少大量判断。（ Y[i] 中的 i 不从 0开始是为了便于处理）。
此处统一约定，对于标志数组 L,R,Y，值为 1 表示占用，值为 0表示未占用。以L为例，L[i]=1表示正斜线i被占用。
4.2 代码实现
/**
* N皇后问题：标记优化（所有下标均从1开始）
* @param n 皇后的数量
* @return 摆法的数量
*/
int queen(int n) {
// 特判
if (n == 1)return 1;
// 棋盘 当前放置哪个皇后 解的数量
int q[n + 1], k = 1, res = 0;
memset(q, 0, sizeof q);
// 标志数组
int y[n + 1], l[2 * n + 1], r[2 * n];
memset(y, 0, sizeof(y)), memset(l, 0, sizeof(l)), memset(r, 0, sizeof(r));
// 中点位置、当前行最多能放到第几列
int w = (n + 1) >> 1, e;
// N是否为奇数
bool odd = n & 1;
// 开始求解
while (k > 0) {
// 当前行放置下一个位置前，把原来占有的位置释放
if (q[k] != 0)
y[q[k]] = l[k + q[k]] = r[k - q[k] + n] = 0;
// 第k个皇后尝试下一个位置
q[k]++;
// 第一行放置的皇后不能超过中点
if (k == 1)e = w;
// n为奇数且第一行放在中间时，第二行不能超过中间
else if (k == 2 && odd && q[1] == w)e = w - 1;
// 其它情况可以放到中点右边
else e = n;
// 寻找第k行的下一个可以放置的位置
while (q[k] <= e && (y[q[k]] || l[k + q[k]] || r[k - q[k] + n]))q[k]++;
// 已超过当前行的上限E，回溯，返回上一行
if (q[k] > e)--k;
// 找到一个解
else if (k == n) res++;
else {
// 标记所在的列、斜线为不可放置
y[q[k]] = l[k + q[k]] = r[k - q[k] + n] = 1;
// 放置下一行
q[++k] = 0;
}
}
return res << 1;
}
时间复杂度：O(n^n)。
空间复杂度：O(n)。
5. 可用优化
5.1 解题思路
前面两种实现，总是从当前行的第一个位置开始尝试，即使当前行没有位置可以放置，也需尝试完当前行每一个位置，这显然是没有必要的。新增 next 数组，next[i]表示位置 i 的下一个可用位置（可用列），next[0] 表示第一个可用位置，next[i]=0 表示 i 是最后一个可用位置，特别的，next[0]=0 表示无可用位置，此时需要回溯。既然已经知道哪些位置可用，那就不再需要数组 Y 来判断某列是否可用。
5.2 代码实现
/**
* N皇后问题：可用优化（所有下标均从1开始）
* @param n 皇后的数量
* @return 摆法的数量
*/
int queen(int n) {
// 特判
if (n == 1)return 1;
// 棋盘 当前放置哪个皇后 解的数量
int q[n + 1], k = 1, res = 0;
memset(q, 0, sizeof q);
// 中点位置 当前行最多能放到第几列
int w = (n + 1) >> 1, e;
// n是否为奇数
bool odd = n & 1;
// 标志数组
int nex[n + 1], l[2 * n + 1], r[2 * n];
memset(l, 0, sizeof(l)), memset(r, 0, sizeof(r));
// 建立可用列链表
for (int i = nex[n] = 0; i < n; ++i) nex[i] = i + 1;
// 当前节点 cur前驱 临时节点
int cur, pre, t;
// 开始求解
while (k > 0) {
// cur指向第一个可用位置
pre = 0, cur = nex[pre];
// 第一行放置的皇后不能超过中间
if (k == 1)e = w;
// N为奇数且第一行放在中间时，第二行不能超过中间
else if (k == 2 && odd && q[1] == w)e = w - 1;
// 其它情况超过中间
else e = n;
/**
* 寻找第k行的下一个可以放置的位置
* !l[k+cur]&&!r[k-cur+n]&&q[k]<=cur：cur需要满足的条件，q[k]<=cur保证当前行尝试的位置会“一直前进”
* cur=0: 链表为空或者找到最后未发现满足条件的列
* cur>e：cur已超过当前行设定的边界，即基础实现中添加的两个限制条件
* cur&&cur<=E用以限定cur的边界
*/
while (cur && cur <= e && (l[k + cur] || r[k - cur + n] || q[k] > cur))
pre = cur, cur = nex[pre];
// 放置当前行时，把当前行原先占有的位置释放
if (q[k]) {
// 恢复成放置原先位置前的状态
t = nex[q[k]];
nex[q[k]] = nex[t];
nex[t] = q[k];
// 保持pre为cur的前驱
if (nex[q[k]] == cur)pre = q[k];
// 标记所在斜线可放置
l[k + q[k]] = r[k - q[k] + n] = 0;
}
// 未找到合适的列，回溯
if (!cur || cur > e)k--;
// 找到合适的列但当前行是最后一行，放完再回溯
else if (k == n) {
q[k] = cur;
res++, k--;
}
// 找到合适的列但非最后一行，放完后放置下一行
else {
q[k] = cur;
nex[pre] = nex[cur]; // cur已被占用，删除cur
nex[cur] = pre; // 记录前驱，用以恢复到放置前的状态
l[k + cur] = r[k - cur + n] = 1; // 标记所在斜线不可放置
q[++k] = 0; // 放置下一行
}
}
return res << 1;
}
时间复杂度：O(n!)。
空间复杂度：O(n)。
6. 位运算
6.1 解题思路
以 3×3 的棋盘为例，最左上角的左斜线记作第一条左斜线，最右上角的第一条右斜线记作第一条右斜线。为了便于叙述，以下涉及到的二进制均只有 n 位（棋盘大小），第几位是从左往右数。
将列、左斜线（/）、右斜线（\）的可用状态分别用二进制表示，1 表示占用，0 表示可用，以列为例，010 表示第 1,3 列可用，第 2 列占用。
将斜线状态转换为列状态，以左斜线为例，如下表所示
（第 1 条左斜线，第 1 行）= 100 的解释为，若第 1 条左斜线不可用，对于第 1 行的影响是 100，即，第 1 列不能放置，第 2,3 列可以放置。
对于第 i 行而言，必须要放置一个皇后（放置不了就直接回溯了），放置完皇后，其对应左斜线状态必然不是 000，因为放置的这个皇后必然会导致某左斜线不可用，所以，假设第 i 行到第 i+1 行，左斜线状态状态由 A➡B，则 A 必定不为 000，在上表所有状态转换（由第 j 行到第 j+1）中，排除起始状态为 000 的转换，(i,j+1) 可由 (i,j) 左移一位得到。
同理可得，对于右斜线而言，(i,j+1) 可由 (i,j) 右移一位得到。
设考虑第 i 行时，列、左斜线、右斜线状态分别为 C,L,R，则
● 第 i 行可选的位置为 pos = ~(C | L | R) & ((1<<n)-1) 的二进制中 1 对应的列，假设选的是第 k 列，则记为 P，P 的二进制中只有第 k 位为 1。
● 考虑第 i 行时，C = C|P，L = (L|P)<<1，R = (R|P)>>1。
注意，C,L,R 需要始终保持只有 n 位有效，由于整数 int 有 32 位，那么除开低 n 位，其余各位均需保持为 0。
6.2 代码实现
/**
* N皇后问题：位运算
* @param n 皇后的数量
* @return 摆法的数量
*/
int queen((int n) {
int res = 0, mk = (1 << n) - 1, k = 1, pos, p;
// 存放放置各行时的状态
tuple<int, int, int, int> st[n + 2];
// 第一行
st[1] = {0, 0, 0, 0};
while (k > 0) {
/**
* c表示列状态
* l表示左斜线状态
* r表示右斜线状态
* m指示当前行哪些列已经尝试过了
*/
auto [c, l, r, m] = st[k];
// 当前行可放置的位置
pos = ~(c | l | r | m) & mk;
// 无可放置的位置则回溯
if (!pos) {
k--;
continue;
}
// 取pos最低位的1
p = pos & (-pos);
// 记录当前行的位置p已尝试过
st[k] = {c, l, r, m | p};
// 状态传递，初始放置下一行时的状态，尝试放置下一行
if (k < n) st[++k] = {c | p, (l | p) << 1, (r | p) >> 1, 0};
// 放置完毕则记录答案并回溯
else res++, k--;
}
return res;
}
时间复杂度：O(n!)。
空间复杂度：O(n)。
7. 统计与分析
五种解法均采用非递归实现，为了直观比较五种解法的效率，分别统计五种解法在 N=10 到 N=18 的情况下的求解时间（单位为毫秒），测试结果如下表所示。
根据上表数据制作散点图，如图4 所示：
从回溯法到可用优化，通过逐步优化求解方式，求解时间也显著减少。位运算方式与对称优化方式的求解时间相当，N <18 时，位运算的求解时间大于对称优化，但是，由数据可以预见，当 N≥18 时，位运算的求解时间将小于对称优化。
本文转载改编自微信公众号：字节幺零二四
|
完善个人信息