题解 | #八皇后#

#include <bits/stdc++.h>
using namespace std;
vector<string> res;
//判断一下如果皇后放在坐标(x,y)会不会与现有皇后有冲突
bool noattack(int x, int y, int chess[][9]) {
    bool flag = 1; //默认不冲突
    //判断横
    for (int i = 1; i < 9; i++) {
        if (i != y && chess[x][i] == 1) {
            flag = 0;
            break;
        }
    }
    //判断竖
    for (int i = 1; i < 9; i++) {
        if (i != x && chess[i][y] == 1) {
            flag = 0;
            break;
        }
    }
    //处理对角线
    int y1 = y - 1;
    int y2 = y + 1;
    for (int i = x - 1; i > 0; i--) {
        //判断左上方对角线有无冲突
        if (y1 > 0 && chess[i][y1] == 1) {
            flag = 0;
            break;
        }
        //判断右上方对角线有无冲突
        if (y2 < 9 && chess[i][y2] == 1) {
            flag = 0;
            break;
        }
        y1--;
        y2++;
    }
    return flag;
}
void eight_queen(int index, string temp, int chess[][9]) {
    if (index == 9) {//index是纵坐标，默认1,2.....8增长，等到了9就应该收集结果
        res.push_back(temp);//收集结果
        return;
    }
    for (int i = 1; i < 9; i++) {
        //没有冲突的话(index,i)这个位置就可以放置
        if (noattack(index, i, chess)) {
            chess[index][i] = 1;//将这个位置进行标记
            temp += char(i + '0');//加入结果串
            eight_queen(index + 1, temp, chess);
            temp.pop_back();//回溯
            chess[index][i] = 0;//回溯
        }
    }
}
int main() {
    int k;
    while (cin >> k) {
        res.clear();
        string t = "";
        //初始化棋盘
        int chess[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                chess[i][j] = 0;
            }
        }
        //纵坐标从1开始按顺序放入
        eight_queen(1, t, chess);
        //字典序排序
        sort(res.begin(), res.end());
        cout << res[k - 1] << endl;
    }
}
// 64 位输出请用 printf("%lld")