以前每次遇到算法问题都是直接暴力求解，一直以为自己用的是暴力穷举法，现在学了回溯法，发现部分问题其实使用的是回溯法，而不是单纯的暴力穷举。
例如求解一个n皇后问题：
1.使用暴力穷举，由于没有两个皇后能够放在一列上，那么解向量一定是数1，2，····，n的一个排列（第一行n种放法，第二行n-1种，以此类推）。时间复杂度O(n!).
为什么是一维而不是两维？因为没有两个皇后能在同一列，所以只用行标志就可以表示出皇后的位置，简化了问题
2.回溯法，就等于是一个一个的试，从1到n，时间复杂度O(n^n),每一行n种放法，总共n行。
看起来回溯法要比暴力穷举差很多，但是实际上回溯法很多时候实际算法复杂度并没有暴力穷举高。比如4皇后问题中，仅需要341个可能节点中的27个节点就可以找到解，但是暴力穷举实际会慢很多。
换一个思路，比如第一个皇后放在了0位置，暴力穷举第二个皇后放在1位置，那么之后的皇后无论怎么放都是错误的，也就是(n-2)!个向量全部都是错误的，而回溯法面对这种问题，会在之前就直接抛弃这种情况，速度会快很多。不要问为什么暴力穷举为什么不学回溯法那样提前抛弃，因为它是暴力穷举（这还算优化过一次，不然直接O(n^n)）。
总而言之，回溯法并不需要得到所有情况，而且运行过程中会提前抛弃不合要求的情况，所以算法复杂度一般不会到最差的情况。
#include<stdio.h>
#define SIZE 8 //皇后的规模
bool judgeColumn(int positionX, int positionY){//列检验
if(positionX==positionY)
return true; //未通过检验
return false;
}
bool judgeDia(int positionX, int positionY){//对角线检验
if(positionX-positionY==1||positionY-positionX==1)
return true; //未通过检验
return false;
}
int main(){
bool flag=false;
int queen[SIZE]={0};//queen位置全部置为0
int i=1; //从1开始，因为第一个皇后queen[0]已经初始化为0了
while(i<SIZE&&i>=0){
flag=false; //列检验和对角线检验的flag
if(i==0){ //第一个皇后queen[0]不用检验，若是有解直接continue开始下一个queen
i++;
if(queen[0]>=SIZE){
printf("无解");
}
else{
continue;
}
}
while(flag==false&&queen[i]<SIZE){//除第一个皇后外，其他皇后的位置必须通过检验
flag=true;
if(judgeDia(queen[i],queen[i-1])){//与上一个皇后进行对角线检验
queen[i]++; //未通过检验 ，换位置，进行下一次检验
flag=false;
}
else{
for(int j=0;j<i;j++){ //当前皇后与之前的所有皇后进行列检验
if(judgeColumn(queen[i],queen[j])){
queen[i]++; //未通过检验，换位置，进行下一次检验
flag=false;
break;
}
}
}
}
if(queen[i]>=SIZE){ //当前皇后的位置已经超出了棋盘范围
queen[i]=0; //将当前皇后位置置零
i--; //回退到上一个皇后
queen[i]++; //上一个皇后位置加一，继续寻找皇后的位置
}
else //当前皇后通过检验
i++; //寻找下一个皇后的位置
}
for(int k=0;k<SIZE;k++){
printf("%d\n",queen[k]);
}
}
