题解 | 八皇后

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
unordered_set<int> cols;
unordered_set<int> diag1;
unordered_set<int> diag2;
vector<int> ans;
void backtracking(int row, int result) {
    if (row == 8) {
        ans.push_back(result);
        return;
    }
    for (int i = 0; i < 8; i++) {
        if (cols.count(i) != 0) continue;
        if (diag1.count(row + i) != 0) continue;
        if (diag2.count(row - i) != 0) continue;
        cols.insert(i);
        diag1.insert(row + i);
        diag2.insert(row - i);
        backtracking(row + 1, result * 10 + i + 1);
        cols.erase(i);
        diag1.erase(row + i);
        diag2.erase(row - i);
    }
}
int main() {
    backtracking(0, 0);
    int b;
    while (cin >> b) {
        cout << ans[b - 1] << endl;
    }
    return 0;
}

模版答案