(回溯) LeetCode 51. 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

二. 解题思路

本题意思也是十分简单，在一块二维数组中进行分布，要求在一点分布了Q之后，该点所在行，列以及对角就不能再出现Q，你需要输出所有在棋盘上的合法分布。

这个题目看起来比较简单，但是做起来还是有些费劲的，你得遍历枚举所有的可能，然后再每一个点上判断加入Q中是否合法，一听头都大了，不要慌！！我们来用回溯给它秒了！

1. 确定递归参数：首先需要一个chessboard 的一维字符串数组用来存储路径中的值，其次需要一个n 用来记录棋盘的大小，再有就是一个row 记录行数。

2. 确定递归的结束条件：当row == n 的时候就说明已经遍历到最后一行了，可以收集结果并且return了。

3. 单层循环递归：首先得确定在第row 行第 i 列放置皇后(Q) 是合法的(有一个isValid 函数专门判断是否合法)，如果不合法，进行下一次的循环，如果合法，就将该位置放置皇后，然后进行递归处理，等到递归返回之后回溯即可。

4. 判断是否合法函数(isValid)：我们只需要确定该点所在的列和对角上不存在皇后即可，这个函数书写比较简单，具体大家可以看下面的代码。

下图是代码随想录中对具体回溯的一个举例，大家可以参考：

话不多说！！！上代码！！

三. 代码

class Solution {
public:vector<vector<string>> res;bool isValid(vector<string>& chessboard, int n, int col, int row){// 检查列for(int i = 0; i < row; i++){               // 只需要检查 0~row 列有没有Q即可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;}void back(vector<string>& chessboard, int n, int row){if(n == row){res.push_back(chessboard);return;}for(int i = 0; i < n; i++){if(isValid(chessboard, n, i, row)){chessboard[row][i] = 'Q';back(chessboard, n, row + 1);chessboard[row][i] = '.';}}}vector<vector<string>> solveNQueens(int n) {res.clear();vector<string> chessboard(n, string(n, '.'));back(chessboard, n, 0);return res;}
};