回溯CSP-J

💡 核心思想

回溯法是一种系统地搜索所有解的方法：从一条路前进，遇到不满足条件就回退，尝试其他选择。它本质上是带剪枝的 DFS。经典应用：全排列、N 皇后、子集生成。

🎯 直觉理解

回溯就像走迷宫时边走边做记号：选一条路走，走到死胡同就沿记号退回最近的岔路口，换一条没走过的路。退回时要把记号擦掉，否则下次"以为这条路走过"，就漏掉了正确答案。

典型例子八皇后：逐行放皇后，每放一个检查是否冲突，冲突就撤销这一格、试下一列。递归深度 = 决策层数，每层枚举所有可能选项。

记住"选 → 递归 → 撤销"三步。回溯本质是暴力枚举 + 剪枝，数据范围大时必须配合剪枝（见"剪枝"页）才能跑完。

📝 算法流程

1. 做出一个选择
2. 递归搜索
3. 撤销选择（恢复现场）
4. 继续尝试下一个选择

$$\text{全排列数量：} n! \text{，回溯法的时间复杂度通常是指数级}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
int n, col[15], ans = 0;
bool usedCol[30], usedDiag1[30], usedDiag2[30];
void dfs(int row) {
    if (row == n) { ans++; return; }
    for (int c = 0; c < n; c++) {
        if (usedCol[c] || usedDiag1[row-c+n] || usedDiag2[row+c]) continue;
        usedCol[c] = usedDiag1[row-c+n] = usedDiag2[row+c] = true;
        dfs(row + 1);
        usedCol[c] = usedDiag1[row-c+n] = usedDiag2[row+c] = false; // 恢复现场
    }
}
int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目