八皇后问题包含了回溯算法的核心思想 ——试探 - 回溯 - 剪枝：
- 同一行：每行仅放 1 个皇后（按行遍历可天然避免行冲突）；
- 同一列：需标记已占用的列，避免重复使用；
- 对角线：棋盘有两条对角线方向（左上→右下、右上→左下），需分别标记占用状态。
1. 回溯法的核心逻辑
回溯法本质是一种 “暴力搜索的优化方案”，通过深度优先搜索（DFS）试探每一种可能，当发现当前路径无法达到目标时，立即 “回溯” 到上一步，尝试其他路径，避免无效搜索。
对于 8 皇后问题：
- 按行递归：每行仅放 1 个皇后，递归层数 = 棋盘行数（8 层）；
- 按列试探：每一行遍历 8 列，尝试在无冲突的列放置皇后；
- 冲突检测：通过标记数组快速判断列和对角线是否占用（O (1) 时间复杂度）；
- 回溯恢复：递归返回后，撤销当前列和对角线的占用标记，恢复棋盘状态，为下一列试探做准备。
2. 关键优化：冲突检测的标记数组设计
（1）列标记数组colUsed
- 作用：标记某一列是否已放置皇后；
- 大小：8（棋盘列数），索引对应列号（0~7）；
- 状态：
colUsed[col] = true表示第 col 列已占用。
（2）对角线标记数组
棋盘有两条对角线，需分别设计标记数组：
左上→右下对角线（记为 diag1）：同一对角线上的皇后满足
row - col = 常数；- 取值范围：row-col 的结果为 -7~7（8 行 8 列），加 7 转为非负索引（0~14），故数组大小为 15；
- 索引计算：
diag1 = row - col + 7。
右上→左下对角线（记为 diag2）：同一对角线上的皇后满足
row + col = 常数；- 取值范围：row+col 的结果为 0~14，天然非负，数组大小为 15；
- 索引计算：
diag2 = row + col。
通过这三个标记数组，可在 O (1) 时间内完成冲突检测，避免了暴力搜索中 “遍历已放皇后判断冲突” 的 O (n) 复杂度，大幅提升效率。
C++代码实现
#include <iostream>
#include <vector>
using namespace std;
int count = 0; // 统计解的数量
vector<bool> colUsed; // 标记列是否被占用（大小8）
vector<bool> diag1Used; // 标记左上→右下对角线（大小15，2*8-1=15）
vector<bool> diag2Used; // 标记右上→左下对角线（大小15）
vector<vector<char> > chessboard; // 存储棋盘状态：'Q'=皇后，'.'=空位
// 回溯函数：按行处理，用标记数组快速判断冲突
void backtracking(int row) {
// 终止条件：所有8行放完，找到一个合法解
if (row == 8) {
count++; // 解数+1
// 打印当前合法解的棋盘
cout << "===== 第 " << count << " 个合法解 =====" << endl;
for (int i = 0; i < 8; ++i) { // 遍历每一行
for (int j = 0; j < 8; ++j) { // 遍历每一列
cout << chessboard[i][j] << " "; // 打印当前格（加空格更美观）
}
cout << endl; // 一行结束换行
}
cout << "======================" << endl << endl; // 分隔不同解
return;
}
// 遍历当前行的所有列
for (int col = 0; col < 8; ++col) {
// 计算对角线索引（避免负数）
int diag1 = row - col + 7; // 范围：0~14（原row-col范围-7~7，+7转正）
int diag2 = row + col; // 范围：0~14（天然非负）
// 冲突检测：O(1)快速判断（无冲突则继续）
if (!colUsed[col] && !diag1Used[diag1] && !diag2Used[diag2]) {
// 标记当前位置为皇后
chessboard[row][col] = 'Q';
// 标记当前列和对角线为占用
colUsed[col] = true;
diag1Used[diag1] = true;
diag2Used[diag2] = true;
backtracking(row + 1); // 递归处理下一行
// 回溯：撤销标记，恢复状态（为尝试当前行下一列做准备）
colUsed[col] = false;
diag1Used[diag1] = false;
diag2Used[diag2] = false;
chessboard[row][col] = '.'; // 恢复当前位置为空位
}
}
}
/*
...（逐层递归，直到row=8）
→ row=8 → 打印解 → return
← 回到backtracking(7) → 撤销row=7的状态 → 尝试下一列
← 回到backtracking(6) → 撤销row=6的状态 → 尝试下一列
← 回到backtracking(0) → 撤销row=0, col=0的状态 → 尝试col=1
*/
int main() {
// 初始化标记数组（默认false，代表未占用）
colUsed.resize(8, false);
diag1Used.resize(15, false);
diag2Used.resize(15, false);
// 初始化棋盘：8行8列，所有位置默认设为'.'（空位）
chessboard.resize(8, vector<char>(8, '.'));
backtracking(0); // 从第0行（第一行）开始回溯
cout << "剪枝优化回溯法解数：" << count << endl; // 输出总解数（92）
return 0;
}
