本文概览：本文以LeetCode题目"N皇后"为例，讲解如何从暴力DFS优化到按行选择+对角线剪枝的回溯解法

一、题目

N皇后题目

二、题目分析

这题的要求是在 n×n 的网格内放入 n 个皇后，每个皇后的主对角线、副对角线、行、列都只有它一个皇后。

一开始看起来很难，很容易会想到暴力破解：从网格左上角开始，每个格子都尝试放皇后，然后从剩下的符合条件的格子里再选一个，一直这样下去。但这样会导致时间复杂度极高，也就是暴力 DFS。

其实到这大概的思路是有的，不过我们要对这个 DFS 做优化。

思路概览

Java 实现代码如下

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
class Solution {
    private boolean[] cols;
    private boolean[] diag;
    private boolean[] antiDiag;
    private final List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        cols = new boolean[n];
        diag = new boolean[2*n-1];
        antiDiag = new boolean[2*n-1];
        backtrack(0, new ArrayList<>());
        return res;
    }

    private void backtrack(int row, List<String> path) {
        if (row == cols.length) {
            res.add(new ArrayList<>(path));
        }
        for (int col = 0; col < cols.length; col++) {
            if (!check(row, col)) {
                continue;
            }
            cols[col] = true;
            diag[row - col + cols.length - 1] = true;
            antiDiag[row + col] = true;
            path.add(createRow(col));
            backtrack(row + 1, path);
            path.removeLast();
            cols[col] = false;
            diag[row - col + cols.length - 1] = false;
            antiDiag[row + col] = false;
        }
    }

    private String createRow(int col) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cols.length; i++) {
            if (i == col) {
                sb.append('Q');
            } else {
                sb.append('.');
            }
        }
        return sb.toString();
    }

    private boolean check(int row, int col) {
        if (cols[col]) {
            return false;
        }
        if (diag[row - col + cols.length - 1]) {
            return false;
        }
        return !antiDiag[row + col];
    }
}

思路简要说明：

  1. 按行选择：每行选一列，保证行列不重合
  2. 对角线剪枝：主对角线 row-col 相等，副对角线 row+col 相等，用数组记录
  3. 结果创建：每行创建 .Q.. 格式的字符串，回溯时删除

三、思路详解

第一步：为什么不能暴力 DFS

暴力 DFS 的思路是：从 (0,0) 开始，每个格子都尝试放皇后，然后从剩下的格子里再选一个，一直这样。

问题在于：

  1. 时间复杂度极高：n×n 的网格，每个格子都要尝试，时间复杂度是 O((n²)!)
  2. 代码复杂：需要大范围搜索，筛选出下面能选的格子，代码不好编写

所以我们需要优化。

第二步：优化一——按行选择

观察棋盘可以发现：每行和每列必然只有一个皇后。

基于这个性质，我们可以按行选择：第一行选一列，第二行选另一列，这样起码保证了行列不重合，也不必进行麻烦的范围运算。

比如 n=4 时：

1
2
3
4
第 0 行：选第 1 列
第 1 行：选第 3 列
第 2 行：选第 0 列
第 3 行：选第 2 列

这样每行每列都只有一个皇后，比全局范围搜索简单多了。

第三步：优化二——对角线剪枝

按行选择解决了行列的问题，但还有主对角线和副对角线的限制。

观察网格：

1
2
3
4
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

主对角线（左上到右下）：

1
2
3
4
(0,0), (1,1), (2,2), (3,3) → row - col = 0
(0,1), (1,2), (2,3)       → row - col = -1
(1,0), (2,1), (3,2)       → row - col = 1
(2,0), (3,1)              → row - col = 2

处于同一条主对角线的格子，row - col 的值相等。

副对角线（右上到左下）：

1
2
3
4
(0,3), (1,2), (2,1), (3,0) → row + col = 3
(0,2), (1,1), (2,0)        → row + col = 2
(1,3), (2,2), (3,1)        → row + col = 4
(2,3), (3,2)               → row + col = 5

处于同一条副对角线的格子，row + col 的值相等。

所以按顺序遍历 col 的时候，排除掉：

  1. 已经选择的 col
  2. 当前 row - col 在以前的选择中出现过
  3. 当前 row + col 在以前的选择中出现过

就可以实现剪枝优化。

第四步：存储之前的选择

由于每次进行新的一行需要记住之前已经选择的列、主对角线、副对角线，所以需要对应的存储方式。

这里建议用 boolean 数组，因为已经给出了 n 值，可以得知数组长度，减小空间开销，而且 O(1) 查询：

  • cols[n]：记录每列是否有皇后
  • diag[2n-1]：记录主对角线是否有皇后（对角线有 2n-1 条）
  • antiDiag[2n-1]：记录副对角线是否有皇后

为什么主对角线索引要加 n-1？

因为 row - col 的范围是 -(n-1) 到 n-1，数组索引不能为负数，所以加上 n-1 偏移到 0 到 2n-2。

具体来说：

  • 最大值：当 row = n-1, col = 0 时（左下角），row - col = n-1
  • 最小值：当 row = 0, col = n-1 时（右上角），row - col = -(n-1)

所以 row - col 的取值范围是 -(n-1), -(n-2), ..., -1, 0, 1, ..., n-2, n-1，共 2n-1 个值。加上 n-1 后，索引范围变为 0, 1, 2, ..., 2n-2，正好对应数组的 2n-1 个位置。

第五步：创建结果

题目要求返回 List<List<String>> 类型，格式为：

1
2
3
4
[
  [".Q..","...Q","Q...","..Q."],
  ["..Q.","Q...","...Q",".Q.."]
]

每种选择对应一个 List<String>，每个元素是 .Q.. 这种类型。

因此每遍历一行就创建一次：for 循环 n 次，用 StringBuilder 拼接字符串，加入到 path 里面。回溯时删掉刚刚生成的。

第六步：完整执行过程

以 n=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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
backtrack(row=0, path=[])
├── col=0: check(0,0) ✓
│   cols[0]=true, diag[3]=true, antiDiag[0]=true
│   path=["Q..."]
│   backtrack(row=1, path=["Q..."])
│   ├── col=0: check(1,0) ✗ (cols[0]=true)
│   ├── col=1: check(1,1) ✗ (diag[3]=true)
│   ├── col=2: check(1,2) ✓
│   │   cols[2]=true, diag[2]=true, antiDiag[3]=true
│   │   path=["Q...", "...Q"]
│   │   backtrack(row=2, path=["Q...", "...Q"])
│   │   ├── col=0: check(2,0) ✗ (cols[0]=true)
│   │   ├── col=1: check(2,1) ✗ (antiDiag[3]=true)
│   │   ├── col=2: check(2,2) ✗ (cols[2]=true)
│   │   ├── col=3: check(2,3) ✗ (diag[2]=true)
│   │   全部失败，回溯
│   │   cols[2]=false, diag[2]=false, antiDiag[3]=false
│   │   path=["Q..."]
│   ├── col=3: check(1,3) ✗ (antiDiag[0]=true)
│   全部失败，回溯
│   cols[0]=false, diag[3]=false, antiDiag[0]=false
│   path=[]
├── col=1: check(0,1) ✓
│   cols[1]=true, diag[2]=true, antiDiag[1]=true
│   path=[".Q.."]
│   backtrack(row=1, path=[".Q.."])
│   ├── col=0: check(1,0) ✗ (antiDiag[1]=true)
│   ├── col=1: check(1,1) ✗ (cols[1]=true)
│   ├── col=2: check(1,2) ✗ (diag[2]=true)
│   ├── col=3: check(1,3) ✓
│   │   cols[3]=true, diag[1]=true, antiDiag[4]=true
│   │   path=[".Q..", "...Q"]
│   │   backtrack(row=2, path=[".Q..", "...Q"])
│   │   ├── col=0: check(2,0) ✓
│   │   │   cols[0]=true, diag[5]=true, antiDiag[2]=true
│   │   │   path=[".Q..", "...Q", "Q..."]
│   │   │   backtrack(row=3, path=[".Q..", "...Q", "Q..."])
│   │   │   ├── col=0: check(3,0) ✗ (cols[0]=true)
│   │   │   ├── col=1: check(3,1) ✗ (cols[1]=true)
│   │   │   ├── col=2: check(3,2) ✓
│   │   │   │   cols[2]=true, diag[4]=true, antiDiag[5]=true
│   │   │   │   path=[".Q..", "...Q", "Q...", "..Q."]
│   │   │   │   backtrack(row=4, path=[".Q..", "...Q", "Q...", "..Q."])
│   │   │   │   row=4=n，收集结果 ✓ ①
│   │   │   │   回溯
│   │   │   ├── col=3: check(3,3) ✗ (cols[3]=true)
│   │   │   回溯
│   │   ├── col=1: check(2,1) ✗ (cols[1]=true)
│   │   ├── col=2: check(2,2) ✗ (antiDiag[4]=true)
│   │   ├── col=3: check(2,3) ✗ (cols[3]=true)
│   │   回溯
│   回溯
├── col=2: check(0,2) ✓
│   ...（对称过程，得到第 2 个解）
├── col=3: check(0,3) ✓
│   ...（对称过程，得到第 3 个解）

最终结果：2 个解

第七步：和前面题目的对比

题目 选择方式 收集时机 剪枝条件 回溯操作
子集 选或不选 每次进入都收集 无 add/removeLast
组合总和 从 start 开始选 sum == target sum > target add/sum+=/removeLast/sum-=
括号生成 按规则加左/右括号 length == 2n open < n, close < open append/deleteCharAt
分割回文串 从 start 开始切 start == s.length() isPalindrome[start][i] add/removeLast
N 皇后 按行选列 row == n cols, diag, antiDiag add/removeLast + 数组标记/取消

N 皇后的剪枝最复杂，需要同时维护三个数组（列、主对角线、副对角线），但回溯框架和其他题目一样。

四、总结

这题的核心是三个优化：

  1. 按行选择：每行选一列，保证行列不重合
  2. 对角线剪枝：主对角线 row-col 相等，副对角线 row+col 相等，用数组 O(1) 查询
  3. 结果创建：每行创建 .Q.. 格式的字符串

这个思路可以推广到所有"棋盘放置"类题目。