题解 | #八皇后#

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

int lie[20];
int zheng[30];
int ni[30];
int n = 8;
vector<string> res;

/*
void dfs(int step){
    if(到达目的地){
        输出解
        返回
    }
    剪枝（可选）
    for(int i=0;i<枚举数;i++){
        if(满足条件){
            更新状态
            dfs(step+1)
            恢复状态
        }
    }
}
*/

void dfs(int step,string s){
    if (step == n){
        res.push_back(s);
        return;
    }

    for (int j = 0; j < n; ++j) {
        if (!(lie[j] || ni[j+step] || zheng[j-step+n])){
            lie[j] = zheng[j-step+n] = ni[j+step] = 1;
            s += j+1+'0';
            dfs(step+1,s);
            //回溯
            s.erase(s.end()-1);
            lie[j] = zheng[j-step+n] = ni[j+step] = 0;
        }
    }
}

int main(){
    int x;
    while (cin>>x){
        string s;
        res.clear();
        dfs(0,s);
        cout<<res[x-1]<<endl;
    }

    return 0;
}