八皇后（N皇后问题）

详解以后慢慢补，看心情。。。

#include<iostream>
#include<cstring>
using namespace std;
int vis[3][8*8];//vis[0][]表示同一列，vis[1][]和vis[2][]表示两个对角线;
int tot;
void search(int cur)
{
    if(cur==8) tot++;
    for(int i=0;i<8;i++)
    {
        if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+8])
            {
            vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=1;
            search(cur+1);
            vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=0;
        }
    }
}
int main()
{
    tot=0;
    memset(vis,0,sizeof(vis));
    search(0);
    cout<<tot<<endl;
    return 0;
}

下面这个是有注释的，慢慢列举理解吧~~

之前不知道看到哪位博主的，我觉得很可以

//在8*8的棋盘上放n个皇后，返回解法种类的数目
//枚举法(2的64次幂次)和组合生成法(40320次)严重超时，需要一种新的方法
#include<iostream>
#include<cstring>
#include<string>
#define N 8 //8*8棋盘
using namespace std;
int tot,n,vis[3][N*N];
//vis的0，1，2分别用来储存和调用列，主对角线，副对角线的情况
//要求返回解的数目，则定义全局变量tot作为返回值
//解体的关键在于：
//确定一个皇后的位置可行以后，
//将她能辐射到的区域都标记下来
//并递归到下一个皇后
//如果下一个皇后的位置不幸被前几位皇后污染(区域已被标记为1)，
//就需要“退回去”，将此皇后的标记清零，并寻找下一个可行的位置，
//也就是“回溯”
void search(int cur){
    if(cur==n) tot++;
    else for(int i=0;i<N;i++){
        //将第一个皇后确定在0行，然后改变她的列数i以确定其他皇后的位置
        //依此类推，一个萝卜一个坑，一个皇后站一行，每确定一个就cur++一次。
        //当cur==n，即八个皇后都已被安置
        //则已确认一个可行解,tot++记录下来
        //因此，不会出现行的横向攻击，因此i可以表示一整列
        //另外由于副对角线y+x=i;
        //主对角线y-x=i(但会出现y-x<0的情况，使用时需要加N)
        //因此可以用i同时表示列，主、副对角线的情况
        if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+N]){
            //如果这里目前没有被前面的皇后占有
            vis[0][i]=vis[1][cur+i]=vis[2][cur-i+N]=1;
            //则由这位皇后污染这片区域(标记为1)
            search(cur+1);
            //并递归下一位皇后
            vis[0][i]=vis[1][cur+i]=vis[2][cur-i+N]=0;
            //最重要的一步 ! ! ! ! ! !
            //既是给错误解留条后路，也为继续搜寻正确解留条活路
            //（事实上这两步的区别就在于是否“tot++”）
            //总之，“改回来”这一步一定要有!!!!!
        }
    }
}
int main(void){
    cin>>n;//输入需要安置的皇后数n
    tot=0;//将tot清零
    memset(vis,0,sizeof(vis));
    //将标记数组vis清零
    search(0);//调用函数得到解的个数tot
    cout<<tot<<endl;//输出
    return 0;
}