题解 | #八皇后#

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n;
vector<string> k;
int a[9];
bool ok(int row,int pos){//pos:当前行的列位置;row:当前行数
    if(row==1)
        return true;
    for(int i=1;i<row;i++){
        if(a[i]==pos){//同列
            return false;
        }
        else if(a[i]-pos==i-row||i-row==-(a[i]-pos)){//斜线
            return false;
        }
    }
    return true;
}
void dfs(int row,int iter){
    for(int i=1;i<=8;i++){
        if(ok(row,i)){
            a[row]=i;         
            if(row!=8){
                dfs(row+1,iter);
            }
            else{
                iter++;
                if(iter<=n){
                    string res="";
                    for(int k=1;k<9;k++){
                        res+=a[k]+'0';
                    }
                    k.push_back(res);
                    
                }
                else return;
            }    
        }
    }
}
int main() {
    while (cin >> n) { // 注意 while 处理多个 case
        memset(a,0,sizeof(a));
        k.clear();
        dfs(1,0);
        cout<<k[n-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")