题目:
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位
/*
复习一下回溯算法的模板:
void backtracking(参数)
{
if(终止条件)
{
存放结果;
return
}
for(选择:本层集合元素(树中节点孩子的数量就是集合的大小))
{
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
*/
class Solution {
private:
vector<vector<string>> result;
// 验证是否合法的函数 1、不能同行 2、不能同列 3、不能同斜线(45度和135度)
// 代码为什么不在同行搜索是否有皇后呢???
// 因为在单层搜索的过程中,每一层递归,只会选for循环(也就是同一行)里的一个元素,所以不用去重了。
bool isValid(int row, int col, vector<string>& chessboard, int n)
{
int count = 0;
// 检查列,相当于一个剪枝操作
for(int i = 0; i < row; i++)
{
// 遍历这一列的每一行
if(chessboard[i][col] == 'Q')
{
return false;
}
}
// 检查 左上角 135度方向 是否有皇后
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--)
{
if(chessboard[i][j] == 'Q')
{
return false;
}
}
// 检查 右上角 45度方向 是否有皇后
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
{
if(chessboard[i][j] == 'Q')
{
return false;
}
}
return true;
}
// row 代表行数
void backtracking(int n, int row, vector<string>& chessboard)
{
// 终止条件: 当递归到棋盘最底层,也就是叶子节点的时候,就可以收集结果并返回了
if(row == n)
{
result.push_back(chessboard);
return;
}
// 单层搜索的逻辑,注意递归的深度就是 row 控制棋盘的行,每一层里的for循环的 col 控制棋盘的列
// 一个行数,一个列数,就可以确定皇后放置的位置,且每一次都是从0开始的
for(int col = 0; col < n; col++)
{
// 注意这个验证是否合法的函数,这个也写得很妙,把需要的信息都当参数传进来,合法后才放入 chessboard
// 如果不合法,直接下一列计算
if(isValid(row, col, chessboard, n))
{
chessboard[row][col] = 'Q'; // 放置皇后
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.'; // 回溯,撤销皇后
}
}
}
public:
vector<vector<string>> solveNQueens(int n)
{
// 把整个棋盘都初始化为 . 的操作,也真是没有想到的一个点,这样便于后面做各种处理
result.clear();
std::vector<std::string> chessboard(n, std::string(n, '.')); // 好赞
backtracking(n, 0, chessboard);
return result;
}
};