1. 题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释：4 皇后问题存在两个不同的解法。

提示：皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

2. 思路

3. 代码

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        board_ = vector<string>(n, string(n,'.'));
        col_used_ = vector<bool>(n, false);
        diag1_ = vector<bool>(2*n -1, false);
        diag2_ = vector<bool>(2*n -1, false);

        dfsSearch(n, 0);
        return res_;
    }

private:
    vector<vector<string>> res_;
    vector<string> board_;
    // false为可以用，true为已占用
    vector<bool> col_used_;
    vector<bool> diag1_;
    vector<bool> diag2_;

    bool isAvailable(int x, int y, int n){
        return !col_used_[y] && !diag1_[x + y] && !diag2_[x - y + n - 1];
    }

    void putQueen(bool is_put, int x, int y, int n){
        board_[x][y] = is_put ? 'Q' : '.';
        col_used_[y] = is_put;
        diag1_[x+y] = is_put;
        diag2_[x-y+n-1] = is_put;
    }

    void dfsSearch(int n , int raw_num){
        if(raw_num == n){
            res_.push_back(board_);
            return;
        }

        for(int i = 0; i<n; ++i){
            if(isAvailable(raw_num, i, n)){
                putQueen(true, raw_num, i, n);
                dfsSearch(n, raw_num+1);
                putQueen(false, raw_num, i, n);
            }
        }
    }
};

提交结果：

参考@花花酱 (opens new window)的代码

// Author: Huahua
// Runtime: 3 ms
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        sols_.clear();
        board_ = vector<string>(n, string(n, '.'));

        cols_ = vector<int>(n, 0);
        diag1_ = vector<int>(2 * n - 1, 0);
        diag2_ = vector<int>(2 * n - 1, 0);

        nqueens(n, 0);

        return sols_;
    }
private:
    vector<string> board_;
    vector<int> cols_;
    vector<int> diag1_;
    vector<int> diag2_;
    vector<vector<string>> sols_;

    bool available(int x, int y, int n) {
        return !cols_[x]
            && !diag1_[x + y]
            && !diag2_[x - y + n - 1];
    }

    void updateBoard(int x, int y, int n, bool is_put) {
        cols_[x] = is_put;
        diag1_[x + y] = is_put;
        diag2_[x - y + n - 1] = is_put;
        board_[y][x] = is_put ? 'Q' : '.';
    }

    // Try to put the queen on y-th row
    void nqueens(const int n, const int y) {
        if (y == n) {
            // found one solution, add to the ans set
            sols_.push_back(board_);
            return;
        }

        // Try every column
        for (int x = 0; x < n; ++x) {
            if (!available(x, y, n)) continue;
            updateBoard(x, y, n, true);
            nqueens(n, y + 1);
            updateBoard(x, y, n, false);
        }
    }
};

其他