GESP 七级 · GESP 202403 C++ 七级 第 2 题

下面的程序属于哪种算法（ ）。

int pos[8];
void queen(int n) {
    for (int i = 0; i < 8; i++) {
        pos[n] = i;
        bool attacked = false;
        for (int j = 0; j < n; j++)
            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j) {
                attacked = true;
                break;
            }
        if (attacked)
            continue;
        if (n == 7) {
            return;
        } else {
            queen(n + 1);
        }
    }
}

逻辑代数运算：与(∧/×)、或(∨/+)、非(┐/¬)。德摩根律：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。

注意德摩根律的正确应用：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。C++中逻辑运算符有短路求值特性。

【考点】递推｜回溯法｜深度优先搜索

1. 考纲定位 本题对应《GESP C++ 七级》算法模块中"递归与回溯"考点。命题人特意把"八皇后"放在这里，就是卡住一大波只会背结论不会看执行流程的考生——很多人一看到皇后问题就喊"回溯"，但根本分不清回溯和贪心、动态规划的区别。

2. 解题思维 看到函数名 queen 和递归调用 queen(n+1)，立刻能定位到这是一棵解空间树的深度优先遍历：每一层递归对应放置一个皇后，内层循环枚举当前列的合法行。attacked 条件检查的是同一列、两条对角线，满足则回溯（continue），不满足才继续递归。因为递归深度等于皇后数量，且每层都会尝试所有可行位置，这正是 DFS 在解空间树上"一条路走到黑、撞墙再回退"的典型特征。

3. 陷阱拆解 选项 A（贪心）诱人：很多人以为"第一个能放的行就是最优解"，但代码里即使找到合法位置也不会停止，而是继续递归，这是回溯而非贪心。选项 B（动态规划）同样具有迷惑性——DP 要求子问题重叠且最优子结构，八皇后并不满足；这里没有状态压缩或记忆化，只是朴素递归。选项 D（广度优先搜索）则容易被"搜索"二字带偏，但本例用递归栈模拟的是 DFS，而非队列层序遍历。

4. 反命题思维 如果把 n==7 处改成打印解，算法类型不变；若把对角线检查去掉，就变成了"八车问题"，依然属于回溯 DFS；若改用显式栈或迭代写法，依然是深度优先搜索。记住：递归深度 == 解空间树的深度，这就是 DFS 的指纹。