n皇后问题的 C++ 回溯算法教学攻略

一、问题描述

n皇后问题是经典的回溯算法问题。给定一个 n×n 的棋盘，要求在棋盘上放置 n 个皇后，使得任何两个皇后之间不能互相攻击。皇后可以攻击同一行、同一列以及同一对角线上的棋子。我们需要找出所有的合法放置方案并输出方案数。

二、输入输出形式

输入形式

输入一个整数 n，表示皇后的个数和棋盘的大小（n×n）。

输出形式

输出所有的合法放置方案，每个方案占一行，皇后所在的列号用空格分隔。最后输出方案的总数。

三、样例输入输出

样例输入

4

样例输出

复制

2 4 1 3
3 1 4 2
2

四、算法分析与设计

1. 回溯算法

n皇后问题适合使用回溯算法解决。回溯算法通过递归尝试所有可能的解，当发现当前路径无法得到合法解时，会回溯到上一步，尝试其他可能性。

2. 状态表示

• board：一个一维数组，其中 board[i] 表示第 i 行皇后所在的列。

• solutions：一个二维数组，存储所有合法的解决方案。

3. 算法步骤

1. 递归放置皇后：从第一行开始，尝试将皇后放置在每一列，并检查是否与之前放置的皇后冲突。

2. 冲突检查：对于每一列，检查是否与之前行的皇后在同一列或同一对角线上。

3. 记录解决方案：当放置完所有行的皇后时，将当前 board 状态记录为一个解决方案。

4. 输出解决方案：遍历所有解决方案并输出。

五、代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int n;
vector<int> board; // 存储每一行皇后所在的列，board[i] 表示第 i 行皇后所在的列
vector<vector<int>> solutions; // 存储所有解决方案void solve(int row) {if (row == n) {solutions.push_back(board);return;}for (int col = 0; col < n; col++) {// 检查是否可以放置皇后bool valid = true;for (int i = 0; i < row; i++) {// 检查同一列和对角线是否已有皇后if (board[i] == col || abs(i - row) == abs(board[i] - col)) {valid = false;break;}}if (valid) {board[row] = col;solve(row + 1);}}
}void printSolutions() {for (const auto& solution : solutions) {for (int col : solution) {cout << col + 1 << " "; // 输出列号加 1}cout << endl;}cout << solutions.size() << endl;
}int main() {cin >> n;board.resize(n);solve(0); // 从第 0 行开始放置printSolutions();return 0;
}

六、代码解析

1. 初始化

• n：表示皇后的个数和棋盘的大小。

• board：动态调整大小为 n，初始化为一个空数组。

• solutions：存储所有的解决方案。

2. 递归函数 solve

• row：表示当前要放置的行。

• 当 row 等于 n 时，表示所有行的皇后都已放置完成，将当前 board 加入解决方案列表。

• 对每一列进行尝试，检查是否与之前放置的皇后冲突。如果没有冲突，则将皇后放置在当前列，并递归处理下一行。

3. 冲突检查

• 检查当前列是否已经有皇后。

• 检查对角线是否已经有皇后，通过比较行差和列差的绝对值是否相等。

4. 输出解决方案

• 遍历所有解决方案，每个方案的列号加 1（因为列号从 0 开始）。

• 最后输出方案的总数。

七、复杂度分析

1. 时间复杂度

回溯算法的时间复杂度为 O(n!)，因为在最坏情况下需要遍历所有可能的排列组合。

2. 空间复杂度

空间复杂度为 O(n)，用于存储当前棋盘状态和解决方案。

八、总结

n皇后问题是一个经典的回溯算法问题。通过回溯算法，我们可以有效地找到所有合法的解决方案。回溯算法利用递归和冲突检查，逐步构建解决方案，并在发现路径无效时及时回溯。这种方法适用于很多组合优化问题，如排列问题、子集问题等。

希望本攻略能够帮助你理解 n皇后问题的回溯算法解法，并能够在实际问题中应用。如果有任何疑问或需要进一步的解释，请随时提问！