八皇后（回溯法）

八皇后问题是一个十分经典的回溯问题，我们将其分析一下可以发现，八皇后问题其实是一个全排列问题，行号代表排列的下标号，列号代表1~n的数字。求得1~n的全排列，回溯找到其中符合要求的情况，这样最多找8！次，即40320次，很小的一个数据量了。在处理是否符合要求时，要注意是否是不同列、不同主对角线、不同副对角线，不需要判断是否是不同行，因为是列的全排列，肯定在不同的行。难点在于对角线的判断，主对角线：y1-x1 == y2-x2。副对角线：y1+x1 == y2+x2。

八皇后优化效率的方式是加了个辅助的二维数组vis[2][10005]用于在循环内容执行前判断是否符合要求。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int n,tot;
int c[maxn],vis[2][maxn];
void curSearch(int cur){//cur代表行
    if(cur == n) tot++;
    else
    for(int i = 0;i < n;i++){//i代表列
        int ok = 1;
        c[cur] = i;
        for(int j = 0;j < cur;j++){
            if(c[cur] == c[j] || cur-c[cur]==j-c[j] || cur+c[cur]==j+c[j]){
                ok = 0;
                break;
            }
        }
        if(ok) curSearch(cur+1);
    }
}
//优化后的算法
void up_curSearch(int cur){//cur代表行
    if(cur == n) tot++;
    else
    for(int i = 0;i < n;i++){//i代表列
        if(!vis[0][i] && !vis[2][cur-i+n] && !vis[1][cur+i] ){//+n是为了把所有cur-i变为正数
            c[cur] = i;
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
            curSearch(cur+1);
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;//这一步不能丢
        }
    }
}
int main()
{
    cin>>n;
    memset(vis,0,sizeof(vis));
    tot = 0;
    curSearch(0);
    //up_curSearch(0);
    cout<<tot<<endl;
    return 0;
}

最后结果是92种。