题解 | 八皇后

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
//对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。
// 已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
// 给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

//每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

//输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

vector<vector<int>> SQueen;//成功序列数组

void DFSFindQ(vector<int>& queen, int pos) {
    for (int i = 1; i <= 8; i++) { //打算放的列号
        bool flag = true;//表示是否满足条件
        for (int j = 0; j < pos; j++) { //检查已放好的皇后代表的是行号
            if (i == queen[j] || pos - j == queen[j] - i || pos - j == i - queen[j]) {
                flag = false;
                break;
            }
        }
        if (flag == true) {
            queen.push_back(i);
            if (pos == 7) {
                SQueen.push_back(queen);
            } else {
                DFSFindQ(queen, pos + 1);
            }
            queen.pop_back();//此时要撤销当前行已经放置的皇后（即恢复到放置该皇后之前的状态），尝试当前行的其他列放置皇后的可能性。
        }
    }
}


int main() {
    vector<int> queen;//正确的皇后放置列的序号
    DFSFindQ(queen, 0);
    int b;
    scanf("%d", &b);
    for (int i = 0; i < 8; i++) {
        printf("%d", SQueen[b - 1][i]);
    }
    printf("\n");
    return 0;
}