👉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; } };
👉总结👈
本篇博客主要讲解了 N 皇后问题，N 皇后问题算是回溯算法中比较难的题目了，解决 N 皇后问题的关键就是判断皇后之间是否会相互攻击。除此之外，还讲解了用位信息来判断放置皇后的位置限制。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
