一本通-1214：八皇后（搜索+回溯）

【题目描述】 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。

给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

【输入】 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1≤b≤92)。

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

【输入样例】 2 1 92

【输出样例】 15863724 84136275

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n = 8;
vector<int> res(8, -1);
int cnt = 0;
vector<string> queen(92);

bool canPlace(int row, int col)
{
    for (int i = 0; i < row; ++i) {
        if (res[i] == col || abs(row - i) == abs(res[i] - col))
            return false;
    }

    return true;
}

void DFS(int row, int n)
{
    for (int col = 0; col < n; ++col) {
        if (canPlace(row, col)) {
            res[row] = col;
            if (row == n - 1) {
                string s(8, ' ');
                for (int i = 0; i < 8; ++i) s[i] = '0' + res[i] + 1;
                queen[cnt++] = s;
            }
            else DFS(row + 1, n);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    DFS(0, 8);

    while (caseNum--) {
        int num; cin >> num;
        cout << queen[num - 1] << endl;
    }

    return 0;
}