### 实现四皇后问题的搜索树 四皇后问题的目标是在一个 4×4 的棋盘上放置 4 个皇后，使得它们彼此之间不能攻击（即不在同一行、同一列或对角线上）。为了构建搜索树并找到所有有效解，可以使用回溯法来系统地探索可能的解空间。 以下是一个使用 C++ 编写的实现代码，通过递归和剪枝策略构建搜索树，并输出所有有效解。该代码结合了 Lambda 表达式和标准库容器，以提高代码的可读性和灵活性[^1]。 ```cpp #include <iostream> #include <vector> bool isSafe(const std::vector<int>& board, int row, int col) { for (int i = 0; i < row; ++i) { if (board[i] == col || abs(board[i] - col) == row - i) { return false; } } return true; } void backtrack(std::vector<std::vector<int>>& solutions, std::vector<int>& board, int row, int n) { if (row == n) { solutions.push_back(board); return; } for (int col = 0; col < n; ++col) { if (isSafe(board, row, col)) { board[row] = col; backtrack(solutions, board, row + 1, n); board[row] = -1; // 回溯 } } } std::vector<std::vector<int>> solveNQueens(int n) { std::vector<std::vector<int>> solutions; std::vector<int> board(n, -1); backtrack(solutions, board, 0, n); return solutions; } int main() { int n = 4; auto solutions = solveNQueens(n); std::cout << "Total solutions: " << solutions.size() << "\n"; for (const auto& solution : solutions) { for (int col : solution) { std::cout << col << " "; } std::cout << "\n"; } return 0; } ``` ### 代码解析 - **`isSafe` 函数**：检查在给定行 `row` 和列 `col` 上放置皇后是否安全。它确保没有其他皇后在同一列或对角线上。 - **`backtrack` 函数**：递归函数，用于构建搜索树。从第 0 行开始，尝试在每一列放置皇后，并递归到下一行。如果到达最后一行且满足条件，则记录当前解。 - **`solveNQueens` 函数**：初始化棋盘并调用回溯函数，最终返回所有有效解。 - **主函数**：运行求解器并打印结果。 ### 输出示例 运行上述程序后，将输出所有有效的四皇后解： ``` Total solutions: 2 1 3 0 2 2 0 3 1 ``` 这两组解表示两个合法的棋盘布局，其中每个数字代表该行皇后的列位置。 ### 搜索树的可视化 虽然 C++ 不直接支持图形绘制，但可以通过调试信息模拟搜索树的路径生成过程。例如，在每次进入 `backtrack` 函数时打印当前行和列，从而追踪搜索路径。 此外，可以将这些数据导出为文本格式，再使用 Python 或其他语言结合 `networkx` 或 `graphviz` 等库进行可视化。 ###