LeetCode刷题实战51：N 皇后
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 N 皇后，我们先来看题面：
https://leetcode-cn.com/problems/n-queens/
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
题意
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
样例
输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
解题
作者：静水流深ylyang
链接：https://www.jianshu.com/p/bf14e0b9dfb7
n皇后问题当n大于等于4才有讨论意义，而且不只有一个解决方案；
用递归的方法找到每一种解决方案；
在当前解决方案中，遍历每一行的每一列查找可以放置皇后的位置；
在当前行中，遍历每一列的每一个位置，假设当前位置可以放，然后进行合法性判断，合法则放置；
然后再递归判断下一行；
递归结束后，将当前行当前列的位置回溯，置为未放状态，再接着判断当前行下一列，目的是为了找到所有的解决方案。Ps：本文用C++的代码为大家解答
#include<iostream>
#include<vector>
using namespace std;
/*
函数声明
*/
// 解决方案函数
vector<vector<string > > solveNQueens(int n);
// 用深度优先搜索的递归实现进行查找解决方案
void dfs(vector<vector<string > > &res, vector<string > &cur, int &n, int row);
// 判断是否可以在当前的row行col列进行放置的合法性
bool isValid(vector<string> &cur, int &n, int row, int col);
vector<vector<string > > solveNQueens(int n) {
// 解决方案结果集
vector<vector<string > > res;
// 初始化棋盘，所有的位置都没有摆放皇后
vector<string> cur(n, string(n, '.'));
dfs(res, cur, n, 0);
return res;
}
/*
res：返回的解决方案集
cur：当前的一个解决方案
n：n皇后问题
row：当前解决方案的第row行
*/
void dfs(vector<vector<string > > &res, vector<string> &cur, int &n, int row) {
// 当超出行数超出了棋盘，则把这次搜索的结果放入res中。
if (row == n) {
res.push_back(cur);
return;
}
for (int j = 0; j < n; j++) {
// 判断在row行j列处是否可以放一个皇后
if (isValid(cur, n, row, j)) {
// 如果可以，则放一个皇后在（row，j）
cur[row][j] = 'Q';
// 继续在下一行找一个位置放皇后
dfs(res, cur, n, row + 1);
// 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。
// 去判断这一行的下一列是否可以放皇后。
cur[row][j] = '.';
}
}
}
/*
cur：当前解决方案
n：n皇后问题
row：考虑当前解决方案的第row行
col：考虑当前解决方案的第col行
*/
bool isValid(vector<string> &cur, int &n, int row, int col) {
// 检查列
for (int i = 0; i < row; i++) {
if (cur[i][col] == 'Q') {
return false;
}
}
// 检查反斜线（\）
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (cur[i][j] == 'Q') {
return false;
}
}
// 检查斜线（/）
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (cur[i][j] == 'Q') {
return false;
}
}
return true;
}
int main()
{
vector<vector<string > > res = solveNQueens(4);
for(int i=0; i<res.size(); i++)
{
for(int j=0; j<res[0].size(); j++)
cout<<res[i][j]<<endl;
cout<<endl;
}
return 0;
}
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
上期推文：
上一篇： 语录收集