深度搜索的思想就是从初始状态出发，下一步可能有多种状态，选其中一个状态深入，到达新的状态；直到无法继续深入，退回到前一步，转移到其他状态，然后再深入下去。
从例题看DFS递归的使用
将数字排列后给出整数n，将数字1~n排成一列，可以有各种各样的排列方法。
现在请按照词典顺序输出所有的排列方法。
输入格式
包含整数n的一行。
输出格式
按词典顺序输出所有排列方案，每个方案占一行。
数据范围
1n7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
# includeiostreamusingnamespacestd； const int N=10； int n； int path[N]； bool st[N]； voidDFS(intu ) if ) u==n ) ) for ) intI=0； i n； I ) coutpath[i] '； coutendl； 返回； }for(intI=1； i=n； I ) if (！ ST[I]}{path[u]=I； st[i]=true； DFS(u1； path[u]=0； st[i]=false； }}}int main () {cinn； DFS(0； 返回0； )八皇后问题盘上放了八位皇后，以免互相攻击。 此时，由于各皇后的攻击范围与同行同列为同一对角线，因此不能与同行、同列为同一对角线。 输出所有情况的棋盘。 **
许多子节点由于不满足条件，在递归时可以中途停止并返回，这一思想就是回溯，在回溯中用于减少子节点扩展的部分称为剪枝。 将问题分为几个步骤递归求解时，如果未合法选择当前步骤，函数将返回到上一级递归调用。 这种现象称为回溯。 因此，递归枚举算法往往成为回溯法。
解决这个问题的关键是如何进行递归和回溯，难度主要是在扩展子节点时如何构造停止递归返回的条件。 解决问题的想法是每行列举q，递归地推出其他皇后。
n-queen问题是将n个queen放在nn的国际象棋棋盘上，使queen不能互相攻击。 这意味着任何皇后都不能在同一行、同一列或同一斜线上。
请现在给出整数n，输出满足条件的所有棋子的走法。
输入格式
包含整数n的一行。
输出格式
每个解决方案占n行，每行输出长度为n的字符串，表示棋盘的整体状态。
其中，"."表示某个位置方块的状态为空，" q "表示皇后排列在某个位置的方块中。
每个方案输出完成后，输出空行。
数据范围
1n9
输入示例：
4
输出示例：
. Q…
…Q
Q…
…Q
…Q
Q…
…Q
. Q…
# includeiostreamusingnamespacestd； const int N=20； int n； char g[N][N]； bool col[N]、dg[N]、bdg[N]； //列，对角线。 对角线VoidDFS(intu ) if ) u==n ) ) for ) intI=0； i n； I ) puts(g[I]； puts (' )； 返回； }for(intI=0； i n； I ) if (！ col[i]！ dg[u i]！ bdg[n - u i]剪枝{g[u][i]='Q '； //枚举Qcol[i]=dg[u i]=bdg[n - u i]=true； DFS(u1； col[i]=dg[u i]=bdg[n - u i]=false； g[u][i]='.'； //撤消} }int main () ) {cinn； for(intI=0； i n； I ) for(intj=0； j n； j ) g(I ) ) j )='.'； DFS(0； 返回0； }算法复杂度：O(n ! )，每行的放皇后，复杂度o(n )，检查冲突o ) ) n )。 n=10时，已经达到千万位数。 要成为n 11的n皇后问题，需要新的方法。