N皇后

描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例 1：

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

输入：n = 1
输出：[[“Q”]]

提示：

1 <= n <= 9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

当我们在解决N皇后问题时，需要一个棋盘来表示当前的状态。我们可以使用一个二维字符数组board来表示棋盘，其中每个位置的值为”.”或”Q”，分别表示该位置为空或有一个皇后。

我们可以使用回溯算法来解决N皇后问题。回溯算法是一种暴力搜索算法，它通过递归的方式搜索所有可能的解。

在回溯算法中，我们从第一行开始，依次遍历每一列。对于每个位置，我们检查当前位置是否合法。如果合法，则将当前位置置为”Q”，递归到下一行。如果找到一组解，则将其加入结果集。回溯到上一行时，将当前位置置为”.”，继续遍历下一列。

在检查当前位置是否合法时，我们需要分别检查该位置所在的列、45度对角线和135度对角线是否存在皇后。具体来说，我们可以遍历之前的每一行，分别检查当前列、45度对角线和135度对角线是否存在皇后。

最终，我们可以得到所有的解。对于每个解，我们将其保存在结果集中，并返回结果集。

下面是代码中各个函数的详细解释：

• solveNQueens函数：该函数用于求解N皇后问题。它接受一个整数n作为参数，表示棋盘的大小。它返回一个二维字符数组，表示所有的解。
• backtrack函数：该函数是回溯算法的核心函数。它接受三个参数：结果集res、当前棋盘board和当前行row。在该函数中，我们首先检查是否找到一组解，如果找到，则将其加入结果集。然后，我们遍历当前行的每一列，检查当前位置是否合法。如果合法，则将当前位置置为”Q”，递归到下一行。如果找到一组解，则将其加入结果集。回溯到上一行时，将当前位置置为”.”，继续遍历下一列。
• isValid函数：该函数用于检查当前位置是否合法。它接受三个参数：当前棋盘board、当前行row和当前列col。在该函数中，我们分别检查当前列、45度对角线和135度对角线是否存在皇后。具体来说，我们可以遍历之前的每一行，分别检查当前列、45度对角线和135度对角线是否存在皇后。

C++代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res; // 保存结果
        vector<string> board(n, string(n, '.')); // 棋盘，初始化为全"."
        backtrack(res, board, 0); // 回溯求解
        return res;
    }

    void backtrack(vector<vector<string>>& res, 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'; // 将当前位置置为"Q"
            backtrack(res, board, row + 1); // 递归到下一行
            board[row][col] = '.'; // 回溯，将当前位置置为"."
        }
    }

    bool isValid(vector<string>& board, int row, int col) {
        int n = board.size();
        // 检查列是否合法
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线是否合法，右上
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线是否合法，左上
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution s;
    vector<vector<string>> res = s.solveNQueens(4); // 求解4皇后问题
    for (auto& board : res) { // 遍历结果集
        for (auto& row : board) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}