以前每次遇到算法問題都是直接暴力求解，一直以為自己用的是暴力窮舉法，現(xiàn)在學了回溯法，發(fā)現(xiàn)部分問題其實使用的是回溯法，而不是單純的暴力窮舉。
例如求解一個n皇后問題：
1.使用暴力窮舉，由于沒有兩個皇后能夠放在一列上，那么解向量一定是數(shù)1，2，····，n的一個排列（第一行n種放法，第二行n-1種，以此類推）。時間復雜度O(n!).
為什么是一維而不是兩維？因為沒有兩個皇后能在同一列，所以只用行標志就可以表示出皇后的位置，簡化了問題
2.回溯法，就等于是一個一個的試，從1到n，時間復雜度O(n^n),每一行n種放法，總共n行。
看起來回溯法要比暴力窮舉差很多，但是實際上回溯法很多時候?qū)嶋H算法復雜度并沒有暴力窮舉高。比如4皇后問題中，僅需要341個可能節(jié)點中的27個節(jié)點就可以找到解，但是暴力窮舉實際會慢很多。
換一個思路，比如第一個皇后放在了0位置，暴力窮舉第二個皇后放在1位置，那么之后的皇后無論怎么放都是錯誤的，也就是(n-2)!個向量全部都是錯誤的，而回溯法面對這種問題，會在之前就直接拋棄這種情況，速度會快很多。不要問為什么暴力窮舉為什么不學回溯法那樣提前拋棄，因為它是暴力窮舉（這還算優(yōu)化過一次，不然直接O(n^n)）。
總而言之，回溯法并不需要得到所有情況，而且運行過程中會提前拋棄不合要求的情況，所以算法復雜度一般不會到最差的情況。
#include<stdio.h>
#define SIZE 8 //皇后的規(guī)模
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]已經(jīng)初始化為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){ //當前皇后的位置已經(jīng)超出了棋盤范圍
queen[i]=0; //將當前皇后位置置零
i--; //回退到上一個皇后
queen[i]++; //上一個皇后位置加一，繼續(xù)尋找皇后的位置
}
else //當前皇后通過檢驗
i++; //尋找下一個皇后的位置
}
for(int k=0;k<SIZE;k++){
printf("%d\n",queen[k]);
}
}
