C++力扣题目51--N皇后

发布时间:2024年01月20日

51. N皇后

力扣题目链接(opens new window)

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

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

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

示例 1:

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

示例 2:

  • 输入:n = 1
  • 输出:[["Q"]]

#思路

都知道n皇后问题是回溯算法解决的经典问题,但是用回溯解决多了组合、切割、子集、排列问题之后,遇到这种二维矩阵还会有点不知所措。

首先来看一下皇后们的约束条件:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

确定完约束条件,来看看究竟要怎么去搜索皇后们的位置,其实搜索皇后的位置,可以抽象为一棵树。

下面我用一个 3 * 3 的棋盘,将搜索过程抽象为一棵树,如图:

51.N皇后

从图中,可以看出,二维矩阵中矩阵的高就是这棵树的高度,矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件,来回溯搜索这棵树,只要搜索到了树的叶子节点,说明就找到了皇后们的合理位置了

#回溯三部曲

按照我总结的如下回溯模板,我们来依次分析:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

  • 递归函数参数

我依然是定义全局变量二维数组result来记录最终结果。

参数n是棋盘的大小,然后用row来记录当前遍历到棋盘的第几层了。

代码如下:

vector<vector<string>> result;
void backtracking(int n, int row, vector<string>& chessboard) {

  • 递归终止条件

在如下树形结构中:?

51.N皇后

可以看出,当递归到棋盘最底层(也就是叶子节点)的时候,就可以收集结果并返回了。

代码如下:

if (row == n) {
    result.push_back(chessboard);
    return;
}

  • 单层搜索的逻辑

递归深度就是row控制棋盘的行,每一层里for循环的col控制棋盘的列,一行一列,确定了放置皇后的位置。

每次都是要从新的一行的起始位置开始搜,所以都是从0开始。

代码如下:

for (int col = 0; col < n; col++) {
    if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
        chessboard[row][col] = 'Q'; // 放置皇后
        backtracking(n, row + 1, chessboard);
        chessboard[row][col] = '.'; // 回溯,撤销皇后
    }
}

  • 验证棋盘是否合法

按照如下标准去重:

  1. 不能同行
  2. 不能同列
  3. 不能同斜线 (45度和135度角)

代码如下:

bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}


?

在这份代码中,细心的同学可以发现为什么没有在同行进行检查呢?

因为在单层搜索的过程中,每一层递归,只会选for循环(也就是同一行)里的一个元素,所以不用去重了。

那么按照这个模板不难写出如下C++代码:

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯,撤销皇后
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    // 检查列
    for (int i = 0; i < row; i++) { // 这是一个剪枝
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // 检查 45度角是否有皇后
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // 检查 135度角是否有皇后
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}
public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return result;
    }
};


?

  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

可以看出,除了验证棋盘合法性的代码,省下来部分就是按照回溯法模板来的。

#总结

本题是我们解决棋盘问题的第一道题目。

如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手,可能知道要用回溯法,但也不知道该怎么去搜。

这里我明确给出了棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,这样就可以套进回溯法的模板里了

大家可以在仔细体会体会

文章来源:https://blog.csdn.net/weixin_47675625/article/details/135671097
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。