52. N 皇后 II：回溯与方向检查

每一行只能放一个皇后，因此递归的第 row 层只需尝试该行的各列。冲突只可能来自同列、主对角线或副对角线。

状态设计#

由于按行递归，当前行之下尚未放置皇后。检查位置 (r, c) 时，只需向上检查同列、左上对角线和右上对角线。

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
const int N = 10;
5

6
int n, res;
7
int g[N][N];
8

9
int check(int r, int c) {
10

11
    for(int i = r - 1; i >= 0; i --) {
12
        if(g[i][c] == 1) return 0;
13
    }
14

15
    for(int i = r - 1, j = c - 1; i >= 0 && j >= 0; i --, j --) {
16
        if(g[i][j] == 1) return 0;
17
    }
18

19
    for(int i = r - 1, j = c + 1; i >= 0 && j < n; i --, j ++) {
20
        if(g[i][j] == 1) return 0;
21
    }
22

23
    return 1;
24
}
25

26
void dfs(int r) {
27

28
    if(r == n) {
29
        res ++;
30
        return ;
31
    }
32

33
    for(int c = 0; c < n; c ++ ) {
34
        if(check(r, c)) {
35
            g[r][c] = 1;
36
            dfs(r + 1);
37
            g[r][c] = -1;
38
        }
39
    }
40
}
41

42
int main() {
43

44
    cin >> n;
45

46
    for(int i = 0; i < n; i ++)
47
        for(int j = 0; j < n; j ++)
48
            g[i][j] = -1;
49

50
    dfs(0);
51

52
    cout << res << "\n";
53

54
    return res;
55
}

回溯最重要的是撤销状态；忘记恢复任一数组都会污染下一条搜索分支。搜索树最坏规模为 $O(n!)$ ，剪枝显著减少实际分支。