八皇后问题（dfs,回溯）

问题地址：

https://www.luogu.com.cn/problem/P1219

解析：

1.每个皇后所在的行、列、两条对角线都不能有别的皇后
2.因为要判断出所有的可能，所以要采用深度优先搜索，结束了一种后再搜索同一层的其他情况
3.设置四个数组，a[13],b[13],c[13],d[13]，初始化都为0
a用来储存i行的列值，例如，a[1]=2，第一行的皇后放在2列上
b用来标记j列，例如，b[2]=1，第2列已经有皇后占领
c用来标记左下到右上的对角线，c[i+j]代表的是同一条线
d用来标记左上到右下的对角线，d[i-j+n]代表的是同一条线

上对角线

下对角线

代码

#include<bits/stdc++.h>
using namespace std;
int a[14],b[14],c[28],d[28];
int cnt;//放置方式计数
int n;
void print(){
    if(cnt<=2){//如果超过3个就停止输出，只进行cnt++
        for(int k=1;k<=n;k++){
            cout<<a[k]<<" ";
        }
        cout<<endl;
    }
    cnt++;
}
void queen(int i){
    if(i>n){//如果走完全部的n行，dfs到底了
        print();
        return;
    }else{
        for(int j=1;j<=n;j++){
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n])){
//如果列、上下对角线都没被标记
                a[i]=j;//储存列的值
                b[j]=1;//标记
                c[i+j]=1;
                d[i-j+n]=1;
                queen(i+1);//进行下一层
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0; //回到上一步要清除标记，相当于没有标记过（不能影响右侧的搜索）
            }
        }
    }
}
int main(){
    cin>>n;
    queen(1);//第一个皇后的位置
    cout<<cnt;
    return 0;
} 

总结：
本题最主要的就是如何标记，