题解 | #八皇后#

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> store;
bool queeneat(int i,int j,int m,int n){//(i,j)是否会吃掉(m,n)
    if(i==m || j==n) return false;
    int k;
    for(k=1;(i+k)<9 && (j+k)<9;k++){
        if((i+k)==m && (j+k)==n) return false;//false即会吃掉
    }
    for(k=1;(i-k)>0 && (j-k)>0;k++){
        if((i-k)==m && (j-k)==n) return false;
    }
    for(k=1;(i-k)>0 && (j+k)<9;k++){
        if((i-k)==m && (j+k)==n) return false;
    }
    for(k=1;(i+k)<9 && (j-k)>0;k++){
        if((i+k)==m && (j-k)==n) return false;
    }
    return true;
}
bool qjudge(int m,int n,string pre){//(m,n)在前缀下是否有效
    for(int i=0;i<pre.length();i++){
        int par=pre[i]-'0';//行和列号，从1开始
        int col=i+1;
        if(!queeneat(par, col, m, n)) return false;
    }
    return true;
}
void EightQ(string pre){
    if(pre.length()==8){
        store.push_back(pre);
        return;
    }
    bool visit[9];
    for(int i=0;i<9;i++) visit[i]=false;
    visit[0]=true;
    for(int i=0;i<pre.length();i++){
        visit[pre[i]-'0']=true;
    }
    int col=pre.length()+1;
    for(int i=1;i<9;i++){
        if(visit[i]) continue;
        if(qjudge(i,col, pre)){
            char ii='0'+i;
            EightQ(pre+ii);
        }
    }
}
int main() {
    int n;
    EightQ("");
    sort(store.begin(),store.end());
    while(cin>>n){
        cout<<store[n-1]<<endl;
    }
}