题解 | #八皇后#

#include <iostream>
#include <vector>
using namespace std;

const int N=9;
int a[N][N];
bool vis_col[N],vis[N][N];

vector<vector<int>> res_col;

bool check(int row,int col){//判对角线是否有皇后
    for(int i=1;i<row;i++){
        for(int j=1;j<=8;j++){
            if(abs(row-i)==abs(col-j)){
                if(a[i][j]==1){
                    return true;
                }
            }
        }
    }
    return false;
}
void dfs(int u,vector<int> &col){
    if(u==9){
        res_col.push_back(col);
        return ;
    }
    for(int j=1;j<=8;j++){
        if(!vis[u][j]){
            if(!vis_col[j]&&!check(u,j)){
                vis[u][j]=true;
                vis_col[j]=true;
                a[u][j]=1;//放皇后
                col.push_back(j);//记录每一行皇后所在的列数
                dfs(u+1,col);
                //回溯
                vis[u][j]=false;
                vis_col[j]=false;
                a[u][j]=0;
                col.pop_back();
            }
        }
    }
}
int main() {
    int b;
    vector<int> col;
    dfs(1,col);
    while(cin>>b){
        vector<int> res=res_col[b-1];
        for(int i=0;i<res.size();i++){
            cout<<res[i];
        }
        cout<<endl;
    }
    return 0;
}