🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
👉N皇后II👈
n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。注：共行、共列或者共斜线的皇后都会相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
皇后摆放的位置是否同行或者同列是很好判断的，关键是如何判断任意两个皇后是否共斜线。
皇后放在不同行，这个是很容易就能够保证的。那么我们就需要保证皇后放在不同行且不共斜线。那么放入皇后的过程就是一个搜索的过程，搜索皇后之间不会相互攻击的位置。那我们需要将已经放入的皇后的所在位置，保存皇后的位置只需要一个整型数组record就行了，record[i] 的值表示第 i 行的皇后放在了第几列。
class Solution
{
private:
int total = 0; // tatol为N皇后的摆法
bool isValid(const vector<int>& record, int row, int col)
{
// 第i行的皇后
// 判断是否和0行到row-1行的皇后共行、共列或者共斜线
// 如果是,返回false;如果不是,返回true
// 条件col == record[i]表示当前row行和i行的皇后共列
// 两个皇后共斜线时,行标差的绝对值等于列标差的绝对值
// 条件abs(record[i] - col) == abs(row - i)表示两个皇后共斜线
for(int i = 0; i < row; ++i)
{
if(col == record[i] || abs(record[i] - col) == abs(row - i))
return false;
}
return true;
}
void BackTracking(int row, vector<int>& record, int n)
{
// 当row等于n时,表示找到了一种摆法
if(row == n)
{
++total;
return;
}
// 当前在第row行,需要遍历当前行的所有列看是否能放入皇后
for(int col = 0; col < n; ++col)
{
// isValid函数是检查第row行的皇后放在第col列,会不会
// 和之前0到row-1行的皇后共行、共列或者共斜线
// 如果是,认为第row的皇后不能放在第col列,继续判断后面的列能不能放皇后
// 如果不是,认为第row的皇后能放在第col列,递归去放第row+1行的皇后
if(isValid(record, row, col))
{
// record[row]表示第row行的皇后放在了第col列
record[row] = col;
BackTracking(row + 1, record, n);
}
}
}
public:
int totalNQueens(int n)
{
total = 0; // 防止同一个对象调用多次调用该函数
vector<int> record(n);
BackTracking(0, record, n);
return total;
}
};
N 皇后的时间复杂度为 O(N^N)。
上面的解法还是可以进行优化，就是通过位信息来表示皇后的位置。这种优化是比较抽象的，但确实可以提高效率。
以八皇后问题为例，来了解通过位信息来判断皇后之间是否会相互攻击。
class Solution
{
private:
// colLim 列的限制，1的位置不能放皇后，0的位置可以放皇后
// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以放皇后
// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以放皇后
int BackTracking(int limit, int colLim, int leftDiaLim, int rightDiaLim)
{
// limit的低n位比特位全为1,如果colLim等于limit,
// 也就说明n个皇后已经摆放好了,且不会相互攻击
if (colLim == limit)
{
return 1;
}
// colLim | leftDiaLim | rightDiaLim为总限制,1表示不可以放皇后,0表示可以放皇后
// ~(colLim | leftDiaLim | rightDiaLim):1表示可以放皇后,0表示不可以放皇后
// pos中的低n位比特位:1表示该位置可以放皇后,0表示该位置不可以放皇后
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
int mostRightOne = 0;
int ret = 0;
while (pos != 0)
{
// pos & (~pos + 1)可以将pos最右侧的1提取出来
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne; // 减去最右侧的1,尝试在次右侧的1的位置上放皇后
// colLim | mostRightOne 默认在pos最右侧的1的位置放皇后
// (leftDiaLim | mostRightOne) << 1:放皇后之后的左斜线的限制
// 因为要去下一行放皇后了,相当于向左下方移动了,那么(leftDiaLim | mostRightOne) << 1就是下一行放皇后左斜线的限制
// (rightDiaLim | mostRightOne) >> 1:放皇后之后的右斜线的限制
// 因为要去下一行放皇后了,相当于向右下方移动了,那么(rightDiaLim | mostRightOne) >> 1就是下一行放皇后右斜线的限制
ret += BackTracking(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >> 1);
}
return ret;
}
public:
// totalNQueens只能解决1到32个皇后的问题
// 如果想要解决1到64个皇后的问题,可以将limit的类型改成long long
int totalNQueens(int n)
{
if (n < 1 || n > 32)
{
return 0;
}
// 保证limit的低n位比特位全为1
int limit = n == 32 ? -1 : (1 << n) - 1;
return BackTracking(limit, 0, 0, 0);
}
};
👉N皇后👈
N 皇后问题的关键还是判断皇后之间是否会相互攻击。N 皇后这道题和 N皇后II 的思路都是一样的，只是返回的结果不同而已。
class Solution
{
private:
vector<vector<string>> ret;
bool isValid(const vector<int>& record, int row, int col)
{
// 第i行的皇后
// 判断是否和0行到row-1行的皇后共行、共列或者共斜线
// 如果是,返回false;如果不是,返回true
// 条件col == record[i]表示当前row行和i行的皇后共列
// 两个皇后共斜线时,行标差的绝对值等于列标差的绝对值
// 条件abs(record[i] - col) == abs(row - i)表示两个皇后共斜线
for(int i = 0; i < row; ++i)
{
if(col == record[i] || abs(record[i] - col) == abs(row - i))
return false;
}
return true;
}
void BackTracking(int n, int row, vector<string>& chessBoard, vector<int>& record)
{
if(row == n)
{
ret.push_back(chessBoard);
return;
}
for(int col = 0; col < n; ++col)
{
if(isValid(record, row, col))
{
// record[row]表示第row行的皇后放在了第col列
record[row] = col;
chessBoard[row][col] = 'Q'; // 放置皇后
BackTracking(n, row + 1, chessBoard, record);
chessBoard[row][col] = '.'; // 回溯,撤销皇后
}
}
}
public:
vector<vector<string>> solveNQueens(int n)
{
ret.clear(); // 防止用同一个对象多次调用该函数
vector<int> record(n);
std::vector<std::string> chessBoard(n, std::string(n, '.'));
BackTracking(n, 0, chessBoard, record);
return ret;
}
};
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;
}
};
文章来源：https://www.toymoban.com/news/detail-792543.html
👉总结👈
本篇博客主要讲解了 N 皇后问题，N 皇后问题算是回溯算法中比较难的题目了，解决 N 皇后问题的关键就是判断皇后之间是否会相互攻击。除此之外，还讲解了用位信息来判断放置皇后的位置限制。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️文章来源地址https://www.toymoban.com/news/detail-792543.html
到了这里，关于【回溯算法篇】N皇后问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
