八皇后问题：回溯算法精解

八皇后问题包含了回溯算法的核心思想 ——试探 - 回溯 - 剪枝：

• 同一行：每行仅放 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;
}