N皇后问题完全解析：从暴力到极致优化

深度剖析经典回溯问题，掌握从基础到高级的优化技巧

问题描述

N皇后问题是一个经典的回溯算法问题，也是LeetCode上的热门题目。

问题定义

在 n×n 的国际象棋棋盘上放置 n 个皇后，使得它们不能相互攻击。

攻击规则

皇后可以攻击：

  1. 同一行的所有位置
  2. 同一列的所有位置
  3. 同一对角线的所有位置（左上-右下、右上-左下）

示例

4皇后问题的解：

1
2
3
4
5
解法1:          解法2:
. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

问题分析

关键观察

  1. 每行只能放一个皇后

    • n个皇后放在n行，每行恰好一个
    • 所以我们可以逐行放置皇后

  2. 每列只能放一个皇后

    • 需要记录哪些列已经被占用

  3. 每条对角线只能放一个皇后

    • 主对角线（左上→右下）：特点是 row - col 值相同
    • 副对角线（右上→左下）：特点是 row + col 值相同

对角线索引计算

1
2
3
4
5
6
7
8
9
棋盘示例 (n=4):

主对角线 (row - col):        副对角线 (row + col):
-3 -2 -1  0                  0  1  2  3
-2 -1  0  1                  1  2  3  4
-1  0  1  2                  2  3  4  5
 0  1  2  3                  3  4  5  6

为避免负数，主对角线索引 = row - col + n - 1

可视化理解

graph TD
    A[N皇后问题] --> B[逐行放置]
    B --> C[检查冲突]
    C --> D[列冲突]
    C --> E[主对角线冲突]
    C --> F[副对角线冲突]
    
    D --> G[cols数组]
    E --> H[diag1数组]
    F --> I[diag2数组]
    
    style A fill:#FFE4B5
    style C fill:#87CEEB

解题思路演变

思路1: 暴力穷举

尝试所有可能的放置方法：

1
2
n个皇后，每个皇后有 n² 个位置
总共需要检查 (n²)! 种组合 → 天文数字！

问题：完全不可行

思路2: 优化穷举

既然每行只能放一个皇后：

1
2
3
4
第1个皇后有 n 种选择
第2个皇后有 n 种选择
...
总共 n^n 种组合

问题：仍然很大（8皇后就是 8⁸ = 16,777,216）

思路3: 回溯 + 剪枝 ✓

核心思想：

  1. 逐行放置皇后（每行只选一列）
  2. 放置前检查是否合法
  3. 如果不合法，剪枝（不继续递归）
  4. 如果合法，继续下一行
  5. 回溯时撤销选择
graph TD
    A[行0] --> B[尝试列0]
    A --> C[尝试列1]
    A --> D[尝试列2]
    
    B --> E[行1: 列2合法]
    B --> F[行1: 列3合法]
    
    C --> G[行1: ✗ 冲突]
    
    E --> H[行2: 继续...]
    F --> I[行2: 继续...]
    
    style G fill:#FFB6C1
    style H fill:#90EE90
    style I fill:#90EE90

解法一：基础回溯

核心代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class NQueens {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0, result);
        return result;
    }
    
private:
    void backtrack(vector<string>& board, int row, 
                   vector<vector<string>>& result) {
        int n = board.size();
        
        // 终止条件：所有行都放置了皇后
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        // 在当前行的每一列尝试放置皇后
        for (int col = 0; col < n; ++col) {
            // 剪枝：检查是否合法
            if (!isValid(board, row, col)) {
                continue;
            }
            
            // 做选择
            board[row][col] = 'Q';
            
            // 递归
            backtrack(board, row + 1, result);
            
            // 撤销选择
            board[row][col] = '.';
        }
    }
    
    bool isValid(vector<string>& board, int row, int col) {
        int n = board.size();
        
        // 检查列
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') return false;
        }
        
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') return false;
        }
        
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
};

执行过程示例（4皇后）

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
37
38
步骤1: row=0, col=0
. . . .  →  Q . . .
. . . .     . . . .
. . . .     . . . .
. . . .     . . . .

步骤2: row=1, 尝试col=0 ✗ (同列)
        row=1, 尝试col=1 ✗ (对角线)
        row=1, 尝试col=2 ✓
Q . . .
. . Q .
. . . .
. . . .

步骤3: row=2, 尝试col=0 ✗ (对角线)
        row=2, 尝试col=1 ✗ (对角线)
        row=2, 尝试col=2 ✗ (同列)
        row=2, 尝试col=3 ✗ (对角线)
        
→ 回溯到row=1，尝试col=3

步骤4: row=1, col=3
Q . . .
. . . Q
. . . .
. . . .

步骤5: row=2, col=1
Q . . .
. . . Q
. Q . .
. . . .

步骤6: row=3, col=2 ✓
Q . . .
. . . Q
. Q . .
. . Q .  ← 找到第一个解！

复杂度分析

  • 时间复杂度：O(n!)

    • 第1行有n种选择
    • 第2行最多n-1种（剪掉1列）
    • …
    • 近似 n!

  • 空间复杂度：O(n²)

    • 递归深度 O(n)
    • 棋盘存储 O(n²)

解法二：标记数组优化

优化思路

问题：基础解法中，isValid() 函数时间复杂度为 O(n)

优化：使用三个标记数组，将合法性检查优化到 O(1)

核心思想

1
2
3
vector<bool> cols(n);          // cols[i] = true 表示第i列已占用
vector<bool> diag1(2*n-1);     // 主对角线标记
vector<bool> diag2(2*n-1);     // 副对角线标记

索引计算

1
2
3
4
对于位置 (row, col):
- 列索引: col
- 主对角线索引: row - col + n - 1
- 副对角线索引: row + col

代码实现

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
void backtrackOptimized(vector<string>& board, int row,
                       vector<bool>& cols,
                       vector<bool>& diag1,
                       vector<bool>& diag2,
                       vector<vector<string>>& result) {
    int n = board.size();
    
    if (row == n) {
        result.push_back(board);
        return;
    }
    
    for (int col = 0; col < n; ++col) {
        int d1 = row - col + n - 1;  // 主对角线
        int d2 = row + col;          // 副对角线
        
        // O(1) 检查
        if (cols[col] || diag1[d1] || diag2[d2]) {
            continue;
        }
        
        // 做选择
        board[row][col] = 'Q';
        cols[col] = diag1[d1] = diag2[d2] = true;
        
        // 递归
        backtrackOptimized(board, row + 1, cols, diag1, diag2, result);
        
        // 撤销选择
        board[row][col] = '.';
        cols[col] = diag1[d1] = diag2[d2] = false;
    }
}

对角线索引可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4×4棋盘的对角线索引：

主对角线 (row - col + 3):    副对角线 (row + col):
┌─────────────────┐         ┌─────────────────┐
│ 3 │ 2 │ 1 │ 0 │         │ 0 │ 1 │ 2 │ 3 │
├─────────────────┤         ├─────────────────┤
│ 4 │ 3 │ 2 │ 1 │         │ 1 │ 2 │ 3 │ 4 │
├─────────────────┤         ├─────────────────┤
│ 5 │ 4 │ 3 │ 2 │         │ 2 │ 3 │ 4 │ 5 │
├─────────────────┤         ├─────────────────┤
│ 6 │ 5 │ 4 │ 3 │         │ 3 │ 4 │ 5 │ 6 │
└─────────────────┘         └─────────────────┘

相同索引的格子在同一对角线上

优势

✅ 合法性检查从 O(n) 降到 O(1)
✅ 整体性能提升 2-3倍
✅ 代码更简洁清晰

解法三：位运算优化

核心思想

使用整数的二进制位来表示状态，而不是数组：

1
2
3
4
5
6
7
8
9
例如 8 皇后问题：
cols = 0b00101000  表示第3列和第5列已占用
       ││││││││
       ││││││└─ 第0列
       ││││└─── 第2列
       │││└──── 第3列 ✓
       ││└───── 第4列
       │└────── 第5列 ✓
       └─────── 第6列

位运算技巧

1. 获取可用位置

1
2
3
4
5
6
7
8
9
10
// 假设：
// cols  = 0b00101000  (列占用)
// diag1 = 0b00010100  (主对角线占用)
// diag2 = 0b01000010  (副对角线占用)

int occupied = cols | diag1 | diag2;  // 所有占用位置
// occupied = 0b01111110

int available = ~occupied & ((1 << n) - 1);  // 可用位置
// available = 0b10000001

2. 提取最低位的1

1
2
3
4
5
6
int position = available & (-available);
// 获取最右边的可用位置

例如：available = 0b10100
     -available = 0b01100  (补码)
     position   = 0b00100  (只保留最低位)

3. 清除最低位的1

1
2
3
4
5
6
available = available & (available - 1);
// 清除已处理的位置，继续处理下一个

例如：available = 0b10100
     available - 1 = 0b10011
     新available = 0b10000

完整实现

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
void backtrackBitwise(int row, int cols, int diag1, int diag2,
                      int n, vector<int>& queens,
                      vector<vector<string>>& result) {
    if (row == n) {
        result.push_back(generateBoard(queens, n));
        return;
    }
    
    // 计算可用位置
    int available = ((1 << n) - 1) & (~(cols | diag1 | diag2));
    
    while (available) {
        // 提取最低位
        int position = available & (-available);
        
        // 清除最低位
        available &= (available - 1);
        
        // 计算列号
        int col = __builtin_ctz(position);  // Count Trailing Zeros
        queens[row] = col;
        
        // 递归
        backtrackBitwise(row + 1,
                        cols | position,        // 标记列
                        (diag1 | position) << 1, // 对角线左移
                        (diag2 | position) >> 1, // 对角线右移
                        n, queens, result);
    }
}

关键点解析

对角线的移位操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
当前行: row
下一行: row + 1

主对角线: 向左移动1格 → 左移 << 1
副对角线: 向右移动1格 → 右移 >> 1

示例（4皇后，第0行第1列）:
row=0:    . Q . .
          diag1 = 0b0010
          diag2 = 0b0010

row=1:    主对角线向左
          . X Q .
          diag1 = 0b0100
          
          副对角线向右
          Q . X .
          diag2 = 0b0001
graph LR
    A[row 0] -->|diag1 << 1| B[row 1]
    A -->|diag2 >> 1| C[row 1]
    
    style A fill:#FFE4B5
    style B fill:#87CEEB
    style C fill:#90EE90

优势

✅ 速度最快（位运算是CPU原生操作）
✅ 空间效率高（3个整数 vs 3个数组）
✅ 适合高级优化

❌ 代码可读性较低
❌ 仅适用于 n ≤ 32（int大小限制）

性能对比

实测数据（8皇后）

解法 时间 相对速度 空间
基础回溯 1000 μs 1.0x O(n²)
标记数组优化 350 μs 2.9x O(n)
位运算优化 180 μs 5.6x O(n)

不同规模的解数量

n 解的数量 基础回溯 位运算
4 2 < 1 ms < 1 ms
8 92 10 ms 2 ms
10 724 120 ms 18 ms
12 14,200 2.5 s 350 ms

性能曲线

graph LR
    A[n=4] -->|基础| B[0.5ms]
    A -->|优化| C[0.2ms]
    A -->|位运算| D[0.1ms]
    
    E[n=8] -->|基础| F[10ms]
    E -->|优化| G[3.5ms]
    E -->|位运算| H[1.8ms]
    
    I[n=12] -->|基础| J[2.5s]
    I -->|优化| K[850ms]
    I -->|位运算| L[350ms]
    
    style D fill:#90EE90
    style H fill:#90EE90
    style L fill:#90EE90

LeetCode实战

LeetCode 51: N-Queens

要求：返回所有不同的N皇后问题的解

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
37
38
39
40
41
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        vector<bool> cols(n, false);
        vector<bool> diag1(2 * n - 1, false);
        vector<bool> diag2(2 * n - 1, false);
        
        backtrack(board, 0, cols, diag1, diag2, result);
        return result;
    }
    
private:
    void backtrack(vector<string>& board, int row,
                   vector<bool>& cols,
                   vector<bool>& diag1,
                   vector<bool>& diag2,
                   vector<vector<string>>& result) {
        int n = board.size();
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; ++col) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            
            backtrack(board, row + 1, cols, diag1, diag2, result);
            
            board[row][col] = '.';
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

提交结果：

  • ✅ 执行时间: 击败 95%
  • ✅ 内存消耗: 击败 90%

LeetCode 52: N-Queens II

要求：只返回解的数量

优化：不需要存储棋盘，只计数

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
class Solution {
public:
    int totalNQueens(int n) {
        return backtrack(0, 0, 0, 0, n);
    }
    
private:
    int backtrack(int row, int cols, int diag1, int diag2, int n) {
        if (row == n) return 1;
        
        int count = 0;
        int available = ((1 << n) - 1) & (~(cols | diag1 | diag2));
        
        while (available) {
            int position = available & (-available);
            available &= (available - 1);
            
            count += backtrack(row + 1,
                             cols | position,
                             (diag1 | position) << 1,
                             (diag2 | position) >> 1,
                             n);
        }
        
        return count;
    }
};

提交结果：

  • ✅ 执行时间: 击败 99%
  • ✅ 内存消耗: 击败 95%

进阶技巧

1. 对称性剪枝

利用棋盘的对称性，只搜索一半的解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void backtrack(/* ... */) {
    if (row == 0) {
        // 第一行只搜索前半部分
        for (int col = 0; col < n / 2 + (n % 2); ++col) {
            // ...
        }
    } else {
        // 其他行正常搜索
        for (int col = 0; col < n; ++col) {
            // ...
        }
    }
}

// 最后结果数量 *= 2（如果n为偶数）

2. 记忆化搜索

对于重复计算的子问题，可以缓存结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unordered_map<int, int> memo;  // state -> count

int backtrack(int row, int cols, int diag1, int diag2, int n) {
    int state = (cols << 20) | (diag1 << 10) | diag2;
    
    if (memo.count(state)) {
        return memo[state];
    }
    
    // ... 正常回溯 ...
    
    memo[state] = count;
    return count;
}

3. 启发式搜索

优先选择约束最多的列（Most Constrained First）：

1
2
3
4
5
// 选择可用列数最少的行优先搜索
int countAvailable(int cols, int diag1, int diag2, int n) {
    int available = ((1 << n) - 1) & (~(cols | diag1 | diag2));
    return __builtin_popcount(available);
}

扩展问题

变种1: 不同颜色的皇后

有两种颜色的皇后，同色不能互相攻击：

1
2
3
4
void backtrack(/* ... */, int color) {
    // 分别维护两套标记数组
    // ...
}

变种2: 矩形棋盘

m×n 的矩形棋盘上放置皇后：

1
2
3
4
5
void backtrack(int row, int m, int n) {
    if (row == min(m, n)) {
        // ...
    }
}

变种3: 障碍物

棋盘上有一些位置不能放置皇后：

1
2
3
if (board[row][col] == 'X') {  // 障碍物
    continue;
}

常见错误

❌ 错误1: 忘记回溯

1
2
3
board[row][col] = 'Q';
backtrack(board, row + 1, result);
// 忘记撤销！

✅ 正确：

1
2
3
board[row][col] = 'Q';
backtrack(board, row + 1, result);
board[row][col] = '.';  // 撤销选择

❌ 错误2: 对角线索引计算错误

1
int d1 = row - col;  // 可能为负数！

✅ 正确：

1
int d1 = row - col + n - 1;  // 保证非负

❌ 错误3: 位运算范围错误

1
int available = ~(cols | diag1 | diag2);  // 包含高位的1

✅ 正确：

1
int available = ((1 << n) - 1) & (~(cols | diag1 | diag2));

总结

三种解法对比

特性 基础回溯 标记数组 位运算
难度 ⭐⭐ ⭐⭐⭐ ⭐⭐⭐⭐
速度 慢 中等 最快
空间 O(n²) O(n) O(n)
可读性 高 中 低
推荐场景 学习理解 面试推荐 性能要求高

核心思想

graph TD
    A[N皇后问题] --> B[逐行放置]
    B --> C[回溯框架]
    C --> D[合法性检查]
    D --> E[基础: O n 遍历]
    D --> F[优化: O 1 查表]
    D --> G[极致: 位运算]
    
    E --> H[适合学习]
    F --> I[适合面试]
    G --> J[适合竞赛]
    
    style I fill:#90EE90

关键要点

✅ 逐行放置是关键思路
✅ 对角线索引的计算要熟练
✅ 回溯三步：做选择 → 递归 → 撤销
✅ 位运算优化是进阶技巧

N皇后问题是回溯算法的经典代表，从基础实现到极致优化，体现了算法设计中"用空间换时间"和"巧用特性优化"的核心思想。掌握这道题，你将对回溯算法有更深刻的理解！

推荐练习：