题解 | #八皇后#

#include <iostream>

#include <vector>
using namespace std;

const int N = 20;
//dfs(cur_r,cur_c)
//st_1(8);st_2(8)
//st_3(15);st_4(15)

bool st_1[N],st_2[N];//行列状态
bool st_3[N],st_4[N];//斜边状态
//st_3左向右：j-i+8
//st_4右向左：i+j-1
vector<string> ans;

void dfs(int r,string &a){
    if(r>8||r<=0)return;
    for(int i=1;i<=8;i++){
        if(st_1[r]||st_2[i]||st_3[i-r+8]||st_4[r+i-1]){
            continue;
        }
        if(!st_1[r]&&!st_2[i]&&!st_3[i-r+8]&&!st_4[r+i-1]){
            if(r==8){
                a.push_back(i+'0');
                ans.push_back(a);
                a.pop_back();
                return;
            }else{
                a.push_back(i+'0');
                st_1[r]=true,st_2[i]=true,st_3[i-r+8]=true,st_4[r+i-1]=true;
                dfs(r+1,a);
                st_1[r]=false,st_2[i]=false,st_3[i-r+8]=false,st_4[r+i-1]=false;
                a.pop_back();
            }
        }
    }
    return;
}


int main() {
    for(int i=0;i<=N;i++){
        st_1[i]=false;
        st_2[i]=false;
        st_3[i]=false;
        st_4[i]=false;
    }
    string a;
    dfs(1,a);
    int n;
    while(cin>>n){
        cout<<ans[n-1]<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")