C++回溯算法解决N皇后问题

N皇后问题是经典的算法问题，要求在一个N x N的棋盘上放置N个皇后，使得她们彼此之间不能相互攻击。皇后的攻击范围包括所在行、列以及对角线。

本文提供使用C++回溯算法解决N皇后问题的详细代码示例和代码解读，帮助你理解回溯算法的核心思想以及如何运用在实际问题中。

C++代码示例：cpp#include #include

void solveNQueens(int n, int row, std::vector& queens, std::vector<std::vectorstd::string>& solutions) { if (row == n) { std::vectorstd::string solution(n, std::string(n, '.')); for (int i = 0; i < n; ++i) { solution[i][queens[i]] = 'Q'; } solutions.push_back(solution); return; }

for (int col = 0; col < n; ++col) {        bool canPlace = true;        for (int i = 0; i < row; ++i) {            if (queens[i] == col || queens[i] == col + row - i || queens[i] == col - row + i) {                canPlace = false;                break;            }        }        if (canPlace) {            queens[row] = col;            solveNQueens(n, row + 1, queens, solutions);        }    }}

std::vector<std::vectorstd::string> solveNQueens(int n) { std::vector<std::vectorstd::string> solutions; std::vector queens(n, -1); solveNQueens(n, 0, queens, solutions); return solutions;}

int main() { int n; std::cout << '请输入皇后的数量 n：'; std::cin >> n;

std::vector<std::vector<std::string>> solutions = solveNQueens(n);

std::cout << '共有 ' << solutions.size() << ' 种解法：' << std::endl;    for (const auto& solution : solutions) {        for (const auto& row : solution) {            std::cout << row << std::endl;        }        std::cout << std::endl;    }

return 0;}

代码解读：

solveNQueens 函数 (回溯函数): - 接受参数：棋盘大小 n，当前行数 row，保存皇后位置的数组 queens，保存所有解法的二维字符串数组 solutions。 - 当 row == n 时，表示已成功放置所有皇后，将当前棋盘状态保存到 solutions 中并返回。 - 遍历当前行的每一列 col，检查是否可以放置皇后 (不与之前放置的皇后冲突)。 - 若可以放置，记录皇后位置到 queens 数组，并递归调用 solveNQueens 处理下一行。
solveNQueens 函数 (主函数): - 初始化保存所有解法的数组 solutions 和保存皇后位置的数组 queens。 - 调用回溯函数 solveNQueens 开始搜索解。 - 返回所有找到的解法 solutions。
main 函数: - 获取用户输入的皇后数量 n。 - 调用 solveNQueens 函数获取所有解法。 - 打印解法数量和每个解法的具体棋盘布局。

回溯算法核心思想：

回溯算法是一种试错搜索算法，它通过不断尝试所有可能的解决方案来找到问题的解。在N皇后问题中，回溯算法的思路是：

从第一行开始，逐行放置皇后。2. 在每一行中，尝试将皇后放置在不同的列上。3. 每次放置皇后后，检查是否与之前放置的皇后冲突。4. 如果没有冲突，则继续放置下一行的皇后。5. 如果有冲突，则回溯到上一行，尝试将皇后放置在其他列上。6. 重复步骤2-5，直到找到所有解或尝试了所有可能的情况。

总结：

本代码示例清晰地展示了如何使用C++回溯算法解决N皇后问题。理解回溯算法的核心思想对于解决各种组合优化问题都非常有帮助。