1
2
3

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

1
2

输入：n = 1
输出：[["Q"]]

 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

class Solution {
    vector<vector<string> > result; //用来保存结果的环境变量；

public:

    /**
    * ## 解题思路
    * - 回溯法
    * 1. 设`f(r)`: 按行在各个棋盘格子中放置'Q';
    * 2. 当`r>n-1`时，结束；
    **/
    vector<vector<string> > solveNQueens(int n) {
        vector<string> chessBoard(n, string(n, '.'));

        trySetQueens(chessBoard, n, 0);

        return result;
    }

    // 尝试往第r行放置'Q'
    void trySetQueens(vector<string>& chessBoard, int r) {
        int n = chessBoard.size();
        if (r > n-1) { //放置到最后一行后了，表示所有行已放置完，且都是合法的
            result.push_back(chessBoard);   //则记录当前的棋盘
            return;
        }
        //未放置完
        //依次尝试往r行各个cow放置'Q'
        for(int c=0; c<n; c++) {
            //如果当前格子不能放置
            if (!isValid(chessBoard, r, c)) {
                continue;   //跳过当前格子，继续下一个格子
            }
            //当前格子可以放
            chessBoard[r][c] = 'Q';         //当前格子放'Q'
            trySetQueens(chessBoard, r+1);  //接着处理下一行
            chessBoard[r][c] = '.';         //撤销当前格子放置的'Q'

            //继续尝试往当前行下一个格子
        }
    }

    // 检测在(r,c)是否能合法放置'Q'
    bool isValid(vector<string>& chessBoard, int n, int r, int c) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if (chessBoard[i][j] == 'Q' && (i==r || j==c || (i-j)==(r-c) || (i+j)==(r+c)) ) {
                    return false;
                }
            }
        }
        return true;
    }

};

 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
59
60
61
62
63
64
65
66
67
68
69
70

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法+bitmap
    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        /// - 深度优先搜索回溯
        fn dfs(
            n: usize,
            board: &mut Vec<usize>,
            states: (i32, i32, i32),
            res: &mut Vec<Vec<String>>,
        ) {
            let (col_mask, diagonal_45, diagonal_135) = states;
            // 所有行(n行)都已放置了'Q'
            if col_mask == (1 << n) - 1 {
                res.push(decode(n, board)); //记录本轮棋谱
                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();
            }
        }

        /// 解码,将棋盘从Vec<usize>转化为Vec<String>
        fn decode(n: usize, board: &Vec<usize>) -> Vec<String> {
            use std::iter::FromIterator;

            board
                .iter()
                .enumerate()
                .fold(vec![vec!['.'; n]; n], |mut brd, (i, &j)| {
                    brd[i][j] = 'Q';
                    brd
                })
                .iter()
                .map(|x| String::from_iter(x))
                .collect()
        }

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

        res
    }
}
// @lc code=end