1
2
3

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

1
2

输入：n = 1
输出：1

 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

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 深度优先搜索
    pub fn total_n_queens(n: i32) -> i32 {
        fn dfs(n: usize, board: &mut Vec<usize>, states: (i32, i32, i32), res: &mut i32) {
            let (col_mask, diagonal_45, diagonal_135) = states;
            // 所有行(n行)都已放置了'Q'
            if col_mask == (1 << n) - 1 {
                *res += 1;
                return; //结束本轮
            }

            // 依次尝试当前行的各个列位置
            for i in 0..n {
                let bit_info = 1 << i; // 下在当前行的第i列

                // 如果当前行所在的列,两条对角线已经有'Q'了, 则跳过当前位置
                if bit_info & (col_mask | diagonal_45 | diagonal_135) != 0 {
                    continue;
                }

                board.push(i); //在当前行第i列放置一个'Q'

                // 继续试探下一步下法
                dfs(
                    n,
                    board,
                    (
                        (col_mask | bit_info),
                        (diagonal_45 | bit_info) << 1, //整体往右下移一位
                        (diagonal_135 | bit_info) >> 1, //整体往左下移一位
                    ),
                    res,
                );

                // 撤消当前位置的棋(以尝试下一个位置)
                board.pop();
            }
        }

        let mut res = 0;
        dfs(n as usize, &mut vec![], (0, 0, 0), &mut res);

        res
    }
}
// @lc code=end

struct Solution;

 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

class Solution {
    int result;
public:
    /*
    * ## 解题思路
    * * 回溯法
    */
    int totalNQueens(int n) {
        vector<vector<bool>> chessBoard(n, vector(n, false));

        dfs(chessBoard, 0);

        return result;
    }
    void dfs(vector<vector<bool>>& chessBoard, int r) {
        int n = chessBoard.size();
        if (r>n-1) {
            result += 1;
            return;
        }
        for(int c=0; c<n; c++) {
            if (!isValid(chessBoard, r, c)) {
                continue;
            }

            chessBoard[r][c] = true;
            dfs(chessBoard, r+1);
            chessBoard[r][c] = false;
        }
    }
    bool isValid(vector<vector<bool>>& chessBoard, int r, int c) {
        int n = chessBoard.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if (chessBoard[i][j] && ( i==r || (j==c) || (i-j)==(r-c) || (i+j) == (r+c) )) {
                    return false;
                }
            }
        }
        return true;
    }
};