目录
回溯法一般是DFS（深度优先搜索）实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来（隐式处理就是回溯法），常见的是通过某种关系构造出来的搜索树，搜索树一般是排列型搜索树（总结点个数一般为n!级别）和子集型搜索树（总节点个数一般为2^n级别）
排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选（结果与顺序无关）。
DFS从起始节点开始，沿着一条路径尽可能深入的搜索（一条路走到黑），直到无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图或树。
DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。
很多时候DFS和回溯法不必过度区分。
//求1~n的全排列
int a[N];
bool vis[N];
void dfs(int dep)//dep表示深度
{
if (dep == n + 1)//说明前面的n层都已经算完了 直接输出结果
{
for (int i = 1; i <= n; i++)cout << a[i] << ' ';
cout << endl;
return;
}
for (int i = 1; i <= n; ++i)
{
//排除不合法的路径
if (vis[i])continue;//表示数字i是否使用过
//修改状态
vis[i] = true;
a[dep] = i;
//下一层
dfs(dep + 1);
//恢复路径
vis[i] = false;//恢复了现场才能往下一个方式递归
}
}在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。
输入中有一个正整数 N≤10，表示棋盘和皇后的数量
为一个正整数，表示对应输入行的皇后的不同放置数量。
输入
5
输出
10
#include<iostream>
using namespace std;
const int N = 15;
int n,ans = 0;
int vis[N][N];//表示被多少个皇后占用了
void dfs(int dep)
{
if (dep == n + 1)
{
ans++;
return;
}
for (int i = 1; i <= n; i++)
{
if (vis[dep][i])continue;//表示当前位置已经被占用了
//修改状态
for (int _i = 1; _i <= n; _i++)vis[_i][i]++;//dep行和第i列占用掉
for (int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--)vis[_i][_j]++;//斜线 左上
for (int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--)vis[_i][_j]++;//斜线 左下
for (int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++)vis[_i][_j]++;//斜线 右下
for (int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++)vis[_i][_j]++;//斜线 右下
dfs(dep + 1);
//恢复现场
for (int _i = 1; _i <= n; _i++)vis[_i][i]--;//dep行和第i列占用掉
for (int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--)vis[_i][_j]--;//斜线 左上
for (int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--)vis[_i][_j]--;//斜线 左下
for (int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++)vis[_i][_j]--;// 右下
for (int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++)vis[_i][_j]--;//斜线 右下
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans << endl;
return 0;
}