linux网站如何做ip解析,网站icp备案信息如何查询,保定建设厅网站,苏州工业园区限电使用回溯法解决八皇后问题
八皇后问题是一个以国际象棋为背景的问题#xff1a;如何能够在88
的国际象棋棋盘上放置八个皇后#xff0c;使得任何一个皇后都无法直接吃掉其他的皇后#xff1f;为了达到此目的#xff0c;任两个皇后都不能处于同一条横行、纵行或斜线上。这…使用回溯法解决八皇后问题
八皇后问题是一个以国际象棋为背景的问题如何能够在8×8
的国际象棋棋盘上放置八个皇后使得任何一个皇后都无法直接吃掉其他的皇后为了达到此目的任两个皇后都不能处于同一条横行、纵行或斜线上。这个问题可以推广为更一般的n 皇后摆放问题其中棋盘的大小变为n×n 而皇后个数也变成n 。当且仅当n1 或n≥4 时问题有解
#include iostream
#include vectorclass Solution {
private:std::vectorstd::vectorstd::string results; // 存储所有有效的棋盘配置public:std::vectorstd::vectorstd::string solveNQueens(int n) {std::vectorstd::string board(n, std::string(n, .)); // 初始化棋盘全部填充为.backtrack(board, 0); // 从第0行开始回溯return results;}private:void backtrack(std::vectorstd::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::vectorstd::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 个皇后全放进去了找到的解的个数加一。
