N 皇后
进阶N 皇后是"约束检查 + 回溯剪枝"的经典代表。
// 算法讲解
N 皇后
在 N×N 棋盘上放置 N 个皇后，使它们互不攻击。
待机
速度 中
待机 ⌨1vector<int> col, diag1, diag2;
2
3void dfs(int row, int n) {
4 if (row == n) {
5 // found one solution
6 return;
7 }
8 for (int c = 0; c < n; c++) {
9 int d1 = row - c + n;
10 int d2 = row + c;
11 if (col[c] || diag1[d1] || diag2[d2]) continue;
12 col[c] = diag1[d1] = diag2[d2] = 1;
13 dfs(row + 1, n);
14 col[c] = diag1[d1] = diag2[d2] = 0;
15 }
16}
复杂度分析
时间 约 O(n!)
空间 O(n)
最优 剪枝后远小于暴搜
最坏 指数级
算法讲解
N 皇后要求任意两个皇后都不能在同一行、同一列或同一对角线上。
最常见的写法是按行递归：当前行尝试所有列，合法就放置，不合法立即剪枝。
因此它特别适合观察"剪枝为何能显著减少搜索树规模"。
如果把列和两条对角线都用布尔数组记录，判断合法性就能降到 O(1)。