题解 | #八皇后#

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

//输出条件：(int row, int col, int str_num),str_num == b时输出
//DFS条件：b[i][j]对应(i,k), (k,j), (i+k,j+k)均无皇后，则摆放,否则j++
//列数从小到大开始试，则结果亦为从小到大的逆序串
int visited[8][8];
int str_num = 0, b, finish = 0;
stack<int> stk; //保存当前皇后串列号

int CheckCollsion(int row, int col){
    for(int k=0; k<8; ++k){ //列冲突
        if(visited[k][col]) return 1;
    }

    for(int k=0; col+k<8&&row+k<8; ++k){ //主对角线向下冲突
        if(visited[row+k][col+k]) return 1;
    }

    for(int k=0; row-k>=0&&col-k>=0; ++k){ //主对角线向上冲突
        if(visited[row-k][col-k]) return 1;
    }

    for(int k=0; row+k<8&&col-k>=0; ++k){ //副对角线向下冲突
        if(visited[row+k][col-k]) return 1;
    }

    for(int k=0; row-k>=0&&col+k<8; ++k){ //副对角线向上冲突
        if(visited[row-k][col+k]) return 1;
    }

    return 0; //不冲突
}

void DFS(int row){
    if(row == 8){ //找到一个皇后串
        str_num ++;
        if(str_num == b) finish = 1; //是所求的b个串，则结束DFS
        return;
    }

    //剪枝
    int j;
    for(j=0; j<8; ++j){
        if(!visited[row][j]){ //确保未访问且不吃掉其他皇后
            int flag = CheckCollsion(row, j);
            if(flag == 0){
                visited[row][j] = 1;
                stk.push(j);
                DFS(row+1); //查找下一行皇后位置
                if(!finish){
                    stk.pop();
                    visited[row][j] = 0;
                }
                else return;
            }
        }
    }
    if(j == 8) return; //此路不通，退回上一步
}

int main() {
    cin>>b;
    DFS(0);
    stack<int> res;
    while (!stk.empty()) {
        int i = stk.top();
        i += 1;
        res.push(i);
        stk.pop();
    }
    while (!res.empty()) {
        cout<<res.top();
        res.pop();
    }
    return 0;
}