LeetCode刷题复盘笔记——51. N 皇后（一文搞懂回溯解决经典的N皇后问题上篇）

今日主要总结一下，51. N 皇后

题目：51. N 皇后

Leetcode题目地址

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

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

本题重难点

N皇后问题是回溯算法解决的经典问题，这道题的主要难点在于之前排列组合子集问题处理的都是一维集合，而这个题目二维矩阵，第一遇到多少有点不知所措。

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

不能同行
不能同列
不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

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

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

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

这道题每递归一次就是向下一行进行遍历，for循环对应广度遍历这一行的哪一列可以放皇后

一、

正确解法

C++代码

class Solution {
public:
    vector<vector<string>> res;
    vector<string> chessboard;
    bool isvalid(int row, int column, int n, vector<string> &chessboard){
        for(int i = 0; i < n; i++){
            if(chessboard[i][column] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--){//45°对角线检查(左上到右下对角线)
            if(chessboard[i][j] == 'Q'){
                return false;
            }
        }
        for(int i = row - 1, j = column + 1; i >= 0 && j < n; i--, j++){//135°对角线检查(右上到左下对角线)
            if(chessboard[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    void backtracing(vector<string>&chessboard, int n, int row){
        if(row == n){
            res.push_back(chessboard);
            return;
        }
        for(int column = 0; column < n; column++){
            if(isvalid(row, column, n, chessboard)){
                chessboard[row][column] = 'Q';
                backtracing(chessboard, n , row + 1);
                chessboard[row][column] = '.';
            }
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) {
        res.clear();
        chessboard.resize(n, string(n, '.'));
        backtracing(chessboard, n, 0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

在这份代码中，可以发现为什么没有在同行进行检查呢？

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

总结

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

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

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

N皇后问题是回溯算法解决的经典题目，大家好好体会一下！加油！

---

欢迎大家关注本人公众号：编程复盘与思考随笔

(关注后可以免费获得本人在csdn发布的资源源码)

公众号主要记录编程和刷题时的总结复盘笔记和心得！并且分享读书、工作、生活中的一些思考感悟！