八皇后问题

八皇后问题是回溯算法中一个比较经典的问题，回溯算法的思想就是，假如我到达一个有两个叉的分叉路口a和b，首先我尝试这走a这条路，当我走不通的时候，我要回到这个分叉路口，在走b这条路。

八皇后问题有很多求解方式，最容易想到的就是，我不管三七二十一的就将八个皇后每个位置只要是空的都可以将皇后填进来，把代码写出来直接提交给计算机解决，但是这样的效率实在是太低了，即使可以解决这个问题，随着n越来越大，消耗的时间也是增长迅猛的。

有一种优化方式就是，我每一行只放一个皇后，最后只要考虑我放的这一种序列是否符合我想要的结果，如果符合，我就将他输出出来，不符合就放弃，但是这样的效果有两种写法，我最先开始用的方法就是先将这n个元素进行全排列，但是从洛谷上提交后，答案是错的，但n=11时基本上就会超时，下面这个就不会了，因为他是一步步填写的，但我这一步填错的时候，我就直接返回到上一步开始的地方，可以在运行时候直接就进行剪枝。

#include<iostream>
using namespace std;
int t=0;
int c[8];//列坐标
int n=8;
bool isok(int row)
{
    for(int i=0;i!=row;i++){
        if(c[i]==c[row]||i+c[i]==row+c[row]||i-c[i]==row-c[row]){
            return false;
        }
    }
    return true;
}
void queen(int row)
{
    if(row==n){
        t++;
        for(int i=0;i<n;i++){
            cout << c[i] << ' ';
        }
        cout << endl;
        return ;
    }
    else{
        for(int x=0;x!=n;x++){//目的保证不在同一行
            c[row]=x;
            if(isok(row)){
                queen(row+1);
            }
        }
    }
}
int main()
{
    queen(0);
    cout << t;
    return 0;
}

由这个代码我想到了一个全排列的变种

#include<iostream>
using namespace std;
int t=0;
int c[8];//列坐标
int n=8;
bool isok(int row)
{
    for(int i=0;i!=row;i++){
        if(c[i]==c[row]){//只需要将不在同一条对角线的情况去掉就可以了
            return false;
        }
    }
    return true;
}
void queen(int row)
{
    if(row==n){
        t++;
        for(int i=0;i<n;i++){
            cout << c[i] << ' ';
        }
        cout << endl;
        return ;
    }
    else{
        for(int x=0;x!=n;x++){//目的保证不在同一行
            c[row]=x;
            if(isok(row)){
                queen(row+1);
            }
        }
    }
}
int main()
{
    queen(0);
    cout << t;
    return 0;
}

具体思想我是看到这个博主写的，受到的启发，感觉这位博主讲的还是挺透的。

 https://www.cnblogs.com/bigmoyan/p/4521683.html