八皇后(一维)

解题思路:1.首先要明确皇后的限制条件，由题目可知行，列，主对角线，反对角线均不可重复,那不妨设col,diag,rediag一维数组,当然二维数组同样适用

              2.按题目要求只需输出前三个解决方案的位置可以创建一个path[N]通过path[1.....n]存储每一行的皇后的列的坐标

              假设n=6,diag主对角线从x+y(1+1)......x+y(6+6) 总计diag[2~12]的数量，所以空间必须2*N

              根据上方再次假设此时x=2,y=6位置放入皇后,此时diag[8]位置不可使用,所以对应主对角线(3,5),(4,4),(5,3),(6,2)都不可使用，反对角线同理

注意事项: diag,rediag数组的开辟空间必须是2*N,其中反对角线rediag[n+x-y]可以保证数组不越界,且dfs由行开始枚举每一列。所以是不需要行rol
来限制的！
参考代码:

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

const int N=15;

int col[N],diag[2*N],rediag[2*N];

int path[N];

int n,ans,k=3; //棋盘大小与方案总数

void pos(){ //输出前三方案皇后位置

    for(int i=1;i<=n;i++){

        cout<<path[i]<<' ';

    }

    cout<<endl;

}

void dfs(int x,int t){

    if(t==n){

        ans++; //方案加一

        if(k>0){

            k--;

            pos();

        }

    }

    for(int i=1;i<=n;i++){

        if(!col[i] && !diag[x+i] && !rediag[n+x-i]){

            col[i]=1;

            diag[x+i]=1;

            rediag[n+x-i]=1;

            path[x]=i;

            dfs(x+1,t+1);

            col[i]=0;

            diag[x+i]=0;

            rediag[n+x-i]=0;

            path[x]=0;

        }

    }

}

signed main(){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

cin>>n;

dfs(1,0); //x坐标 皇后数量

cout<<ans<<endl;

return 0;

}