回溯法c++学习 解决八皇后问题
使用回溯法解决八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8
的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。这个问题可以推广为更一般的n 皇后摆放问题，其中棋盘的大小变为n×n ，而皇后个数也变成n 。当且仅当n=1 或n≥4
时，问题有解
#include <iostream>
#include <vector>class Solution {
private:std::vector<std::vector<std::string>> results; // 存储所有有效的棋盘配置public:std::vector<std::vector<std::string>> solveNQueens(int n) {std::vector<std::string> board(n, std::string(n, '.')); // 初始化棋盘，全部填充为'.'backtrack(board, 0); // 从第0行开始回溯return results;}private:void backtrack(std::vector<std::string>& board, int row) {if (row == board.size()) { // 如果已经放置了n个皇后（到达最后一行之后），找到一个有效解results.push_back(board);return;}int n = board[row].size();for (int col = 0; col < n; col++) { // 尝试在当前行的每一列放置皇后if (isValid(board, row, col)) { // 检查在此位置放置皇后是否有效board[row][col] = 'Q'; // 放置皇后backtrack(board, row + 1); // 递归到下一行board[row][col] = '.'; // 回溯，撤销这个位置的皇后}}}bool isValid(const std::vector<std::string>& board, int row, int col) {int n = board.size();// 检查同一列for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') return false;}// 检查左上对角线for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q') return false;}// 检查右上对角线for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q') return false;}return true; // 如果通过所有检查，则此位置有效}
};int main() {Solution solution;auto results = solution.solveNQueens(8); // 解决8皇后问题// 打印所有解for (int i = 0; i < results.size(); i++) {std::cout << "Solution " << i + 1 << ":\n";for (const auto& row : results[i]) {std::cout << row << "\n";}std::cout << "\n";}std::cout << "Total solutions: " << results.size() << std::endl;return 0;
}这段代码的详细解释如下：
- 我们定义了一个
Solution类来封装解决方案。 results成员变量用于存储所有有效的棋盘配置。solveNQueens函数是主入口点，它初始化棋盘并开始回溯过程。backtrack函数实现了回溯算法：- 如果已经成功放置了n个皇后，我们就找到了一个有效解。
- 否则，我们尝试在当前行的每一列放置皇后。
- 如果某个位置有效，我们就放置皇后，然后递归到下一行。
- 在回溯时，我们撤销这个位置的皇后。
isValid函数检查在特定位置放置皇后是否有效：- 检查同一列是否已有皇后。
- 检查左上对角线是否已有皇后。
- 检查右上对角线是否已有皇后。
- 在
main函数中，我们创建Solution对象，解决8皇后问题，并打印所有解。
这个算法的时间复杂度是O(N!)，其中N是棋盘的大小（在这里是8）。这是因为在最坏的情况下，我们需要尝试所有可能的排列。空间复杂度是O(N)，主要用于递归调用栈和存储棋盘状态。
这个解决方案使用了回溯法，它通过系统地尝试所有可能的配置来找到所有有效的解。每当发现当前路径不可行时，它就回溯并尝试下一个可能的选择。
但是八皇后问题的最有效的算法是位运算法
#include <iostream>
using namespace std;// 位运算解决八皇后问题
void solveNQueens(int n) {long upperlim = (1 << n) - 1; // 初始化，upperlim 表示 n 个皇后的所有列都已放置好long Ans = 0; // 记录解的个数// 递归函数，寻找可以放置皇后的位置void test(long row, long ld, long rd) {if (row != upperlim) {// pos 表示当前行可以放置皇后的位置long pos = upperlim & (~(row | ld | rd));while (pos) {// 取出最右边的可以放皇后的位置long p = pos & (-pos);pos -= p; // 移除该位置并递归调用 test 过程// 更新限制条件long new_ld = (ld | p) << 1;long new_rd = (rd | p) >> 1;test(row | p, new_ld, new_rd);}} else {++Ans; // 找到一个解}}// 调用参数test(0, 0, 0);cout << "共有 " << Ans << " 种排列" << endl;
}int main() {int n = 8; // 八皇后问题solveNQueens(n);return 0;
}
这段代码使用了位运算来高效地解决八皇后问题。核心思想是用一个整数变量表示每一行中哪些位置已经被占用，然后通过位运算判断某个位置是否可以放置皇后。具体解释如下：
upperlim初始化为2n−1，表示 n 个皇后的所有列都已放置好。test函数是递归的，它寻找可以放置皇后的位置。参数row、ld和rd分别表示在纵列和两个对角线方向的限制条件下，这一行的哪些地方不能放。- 位于该行上的冲突位置用
row、ld和rd中的 1 来表示。将它们三个进行并操作，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos表示）。 p = pos & (-pos)取出pos最右边的那个 1，表示该行的某个可以放子的位置。将它从pos中移除并递归调用test过程。- 注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。
- 最后，如果递归到某个时候发现
row = upperlim，说明 n 个皇后全放进去了，找到的解的个数加一。