【回溯算法篇】N皇后问题

🌠作者：@阿亮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 longint totalNQueens(int n){if (n < 1 || n > 32){return 0;}// 保证limit的低n位比特位全为1int 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;}
};