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

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

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

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

示例：

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

提示：

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

Solution

• 套用回溯算法框架

参考 回溯算法解题套路框架 的思路

# @lc code=start
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [['.' for _ in range(n)] for _ in range(n)]

        res = []
        def backtrack(board, row):
            # 触发条件
            if row == len(board):
                res.append(["".join(board[i]) for i in range(len(board))])
                return
            n = len(board[row])
            for col in range(n):
                # 排除不合法选项
                if not isPlace(board, row, col):
                    continue
                # 选择
                board[row][col] = 'Q'
                # 进行下一次决策
                backtrack(board, row+1)
                # 撤销选择
                board[row][col] = '.'

        def isPlace(board, row, col):
            n = len(board)
            for i in range(n):
                if board[i][col] == 'Q':
                    return False
            i,j = row-1, col-1
            while i>=0 and j>=0:
                if board[i][j] == 'Q':
                    return False
                i,j = i-1, j-1
            i,j = row-1, col+1
            while i>=0 and j<n:
                if board[i][j] == 'Q':
                    return False
                i,j = i-1, j+1
            return True

        backtrack(board, 0)
        return res
# @lc code=end

cpp

// @lc code=start
class Solution {
private:
    vector<vector<string>> res;

    void dfs(vector<string>& board, int row){
        if(row==board.size()){
            res.push_back(board);
            return;
        }

        int n = board[row].size();
        for(int col=0; col<n; ++col){
            if(!isValid(board, row, col))
                continue;
            board[row][col] = 'Q';
            dfs(board, row+1);
            board[row][col] = '.';
        }
    }

    bool isValid(vector<string>& board, int row, int col){
        int m=board.size();
        // 检查当前列是否冲突
        for(int i=0; i<row; ++i){
            if(board[i][col]=='Q') return false;
        }
        // 检查右上方是否冲突
        for(int i=row-1, j=col+1; i>=0 && j<m; 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;
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(board, 0);
        return res;
    }
};
// @lc code=end

拓展

对于找到一种解就结束的情况，回溯算法

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return true;
    }
    ...
    for (int col = 0; col < n; col++) {
        ...
        board[row][col] = 'Q';

        if (backtrack(board, row + 1))
            return true;

        board[row][col] = '.';
    }
    return false;
}