解题思路

首先我们可以确定一下回溯传入值

backtracking(row: int, uMap: defaultdict(int), path:list[str])

这里row是行的意思，我们传入行不断的增加以达到每个皇后不在同一行上

uMap中key是col，value是row。

计算斜角是否在攻击范围内就是当前的row - preRow == col - preCol

代码

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        
        def backtracking(row: int, umap:defaultdict(int), path:list[str]):
            if row == n:
                result.append(path.copy())
                return
            s = ['.'] * n
            for col in range(0, n):
                flag = False
                for pre_col, pre_row in umap.items():
                    if abs(row - pre_row) == abs(col - pre_col):
                        flag = True
                        break
                if col in umap: continue  # 该列会被攻击到
                if flag: continue  # 会被斜角攻击到
                s[col] = 'Q'
                umap[col] = row
                path.append("".join(s))
                backtracking(row + 1, umap, path)
                s[col] = '.'
                path.pop()
                umap.pop(col)
        
        backtracking(0, defaultdict(int), [])
        return result

C++

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:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<int> col(n), on_path(n), diag1(n * 2 - 1), diag2(n * 2 - 1);
        function<void(int)> dfs = [&](int r) {
            if (r == n) {
                vector<string> board(n);
                for (int i = 0; i < n; ++i)
                    board[i] = string(col[i], '.') + 'Q' + string(n - 1 - col[i], '.');
                ans.emplace_back(board);
                return;
            }
            for (int c = 0; c < n; ++c) {
                int rc = r - c + n - 1;
                if (!on_path[c] && !diag1[r + c] && !diag2[rc]) {
                    col[r] = c;
                    on_path[c] = diag1[r + c] = diag2[rc] = true;
                    dfs(r + 1);
                    on_path[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
                }
            }
        };
        dfs(0);
        return ans;
    }
};

Go

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
var result [][]string
var path []string
func solveNQueens(n int) [][]string {
    result = [][]string{}
    path = []string{}
    umap := make(map[int]int)
    backtracking(0, umap, n)
    return result
}

func backtracking(row int, umap map[int]int, n int) {
    if row == n {
        t := make([]string, len(path))
        copy(t, path)
        result = append(result, t)
        return
    }
    s := make([]rune, n, n)
    for i, _ := range s {
        s[i] = '.'
    }
    for col := 0; col < n; col++ {
        _, ok := umap[col]
        flag := false
        for pre_col, pre_row := range umap {
            if abs(row - pre_row) == abs(col - pre_col) {
                flag = true
                break
            }
        }
        if flag {continue}
        if ok {continue}
        s[col] = 'Q'
        umap[col] = row
        path = append(path, string(s))
        backtracking(row + 1, umap, n)
        s[col] = '.'
        delete(umap, col)
        path = path[:len(path) - 1]
    }
}

func abs(a int) int{
    if a < 0 {return -a}
    return a
}