暴力穷举和回溯法（八皇后问题）

以前每次遇到算法问题都是直接暴力求解，一直以为自己用的是暴力穷举法，现在学了回溯法，发现部分问题其实使用的是回溯法，而不是单纯的暴力穷举。

例如求解一个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]);
    }
}

第一次用Markdown(2018/11/30),吐血，为什么就是不能上传公式