回溯CSP-S

💡 核心思想

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

🎯 直觉理解

回溯就像走迷宫：你选择一条路，边走边做标记。走到死胡同，沿标记退回最近的岔路口，换条路走。关键是退回时要把标记擦掉，否则别的路也走不了了。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
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;
}

⚠️ 常见坑点

📚 相关题目