跳转至

51.N 皇后 (Hard)*

题目描述*

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

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

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

示例*

输入: 4

输出: 

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

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

代码*

经典回溯问题，觉得 isValid 函数遍历验证太麻烦，可以用 unordered_set 保证列、主副对角线无冲突。即对应 col、row + col（右上）、row - col（左上）。

class Solution {
private:
    vector<vector<string>> results;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        backtracking(board, 0);
        return results;
    }
    void backtracking(vector<string>& board, int i) {
        if(i == board.size()) {
            results.push_back(board);
        }else {
            for(int j = 0; j < board[i].size(); j++) {
                if(!isValid(board, i, j)) {
                    continue;
                }
                board[i][j] = 'Q';
                backtracking(board, i + 1);
                board[i][j] = '.';
            }
        }
    }
    bool isValid(vector<string>& board, int row, int col) {
        for(int i = 0; i < board.size(); i++) {
            if(board[i][col] == 'Q') {
                return false;
            }
        }
        // 右上
        for(int i = row - 1, j = col + 1; i >= 0 && j <board.size(); i--, j++) {
            if(board[i][j] == 'Q'){
                return false;
            }
        }
        // 左上
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if(board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

class Solution {
private:
    vector<vector<string>> results;
    unordered_set<int> col;
    unordered_set<int> rightUp;
    unordered_set<int> leftUp;
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        backtracking(board, 0);
        return results;
    }
    void backtracking(vector<string>& board, int i) {
        if(i == board.size()) {
            results.push_back(board);
        }else {
            for(int j = 0; j < board[i].size(); j++) {
                // if(!isValid(board, i, j)) {
                if(col.find(j) != col.end() || 
                    rightUp.find(i + j) != rightUp.end() || 
                    leftUp.find(i - j) != leftUp.end()) {
                    continue;
                }
                board[i][j] = 'Q';
                col.insert(j);
                rightUp.insert(i + j);
                leftUp.insert(i - j);
                backtracking(board, i + 1);
                leftUp.erase(i - j);
                rightUp.erase(i + j);
                col.erase(j);
                board[i][j] = '.';
            }
        }
    }
};
最后更新: July 23, 2022