N 皇后

题意

在 $n \times n$ 棋盘上放置 $n$ 个皇后，使任意两个皇后不在同一行、同一列或同一斜线上。返回所有合法方案的棋盘表示。

思路

最直接的思路是枚举每行皇后放在哪一列，全部决定后再检查冲突：

cpp

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// brute.cpp：小数据暴力解，递归枚举每一行的皇后放在哪一列。
#include <bits/stdc++.h>
using namespace std;

int n;
int place[10]; // place[r] = c 表示第 r 行皇后在第 c 列
vector<vector<string>> ans;

bool check() {
    for (int r1 = 0; r1 < n; r1++)
        for (int r2 = r1 + 1; r2 < n; r2++)
            if (place[r1] == place[r2] || abs(place[r1] - place[r2]) == r2 - r1)
                return false;
    return true;
}

void dfs(int r) {
    if (r == n) {
        if (check()) {
            vector<string> board(n, string(n, '.'));
            for (int i = 0; i < n; i++)
                board[i][place[i]] = 'Q';
            ans.push_back(board);
        }
        return;
    }
    for (int c = 0; c < n; c++) {
        place[r] = c;
        dfs(r + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(0);
    for (auto &v : ans) {
        for (auto &s : v)
            cout << s << '\n';
        cout << '\n';
    }
    return 0;
}

brute.cpp 先生成完整排列再检查冲突，复杂度 $O(n^n)$ ，对 $n \geqslant 8$ 会超时。

优化的关键是：逐行放置时用三个冲突集合实时剪枝。

col[c]：第 c 列是否已有皇后。
diag1[r+c]：主对角线（左上到右下）是否已有皇后。同一主对角线上的格子满足 r+c 相等。
diag2[r-c+n-1]：副对角线（右上到左下）是否已有皇后。同一副对角线上的格子满足 r-c 相等（偏移 n-1 避免负下标）。

每行只放一个皇后，所以行冲突天然不存在。三个数组实时标记当前占据的列和对角线，放置前检查、放置后标记、递归后恢复，保证每一步只扩展合法分支。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<int> col(n), diag1(2 * n - 1), diag2(2 * n - 1);
        vector<string> board(n, string(n, '.'));
        function<void(int)> dfs = [&](int r) {
            if (r == n) {
                ans.push_back(board);
                return;
            }
            for (int c = 0; c < n; c++) {
                // 同一主、副对角线上的格子分别共享 r+c 和 r-c+n-1。
                int d1 = r + c, d2 = r - c + n - 1;
                if (col[c] || diag1[d1] || diag2[d2])
                    continue;
                col[c] = diag1[d1] = diag2[d2] = 1;
                board[r][c] = 'Q';
                dfs(r + 1);
                board[r][c] = '.';
                col[c] = diag1[d1] = diag2[d2] = 0;
            }
        };
        dfs(0);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (auto &v : Solution().solveNQueens(n)) {
        for (auto &s : v)
            cout << s << '\n';
        cout << '\n';
    }
    return 0;
}

python

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#!/usr/bin/env python3
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans, board = [], ["." * n for _ in range(n)]
        col, d1, d2 = [0] * n, [0] * (2 * n - 1), [0] * (2 * n - 1)

        def dfs(r):
            if r == n:
                ans.append(board[:])
                return
            for c in range(n):
                if col[c] or d1[r + c] or d2[r - c + n - 1]:
                    continue
                col[c] = d1[r + c] = d2[r - c + n - 1] = 1
                lst = list(board[r])
                lst[c] = "Q"
                board[r] = "".join(lst)
                dfs(r + 1)
                lst[c] = "."
                board[r] = "".join(lst)
                col[c] = d1[r + c] = d2[r - c + n - 1] = 0

        dfs(0)
        return ans


def main():
    n = int(input())
    for v in Solution().solveNQueens(n):
        for s in v:
            print(s)
        print()


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n!)$ ，第一行 n 个选择，第二行最多 n-1 个，逐行递减。
空间复杂度： $O(n)$ ，三个冲突数组加递归栈。

总结

N 皇后是回溯剪枝的经典模型。关键是用 col、diag1、diag2 三个数组将冲突检测从 $O(n)$ 降到 $O(1)$ 。对角线的下标定义：主对角线 r+c，副对角线 r-c+n-1，使得同一对角线上所有格子的下标相等。

目录

题意

思路

代码

复杂度

总结