题解 | #八皇后#

//土尔逊Torson 编写于2023/06/16
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stdlib.h>

using namespace std;
//a:棋盘当前的状态  row[i]:第i行有元素  col[i]:第j列有元素
//eye1：主对角线(x+n-y定值)  eye2：次对角线(x+y定值)
const int MAX = 9;

long long row[MAX], col[MAX], eye1[MAX * 3], eye2[MAX * 3], n = 8, res = 0, b;
vector<string> v;

void dfs12501(long long x, string s) {//对第x行进行搜索
	if (x == n + 1) { res++; v.push_back(s); return; }//成功凑成n皇后
	for (int i = 1; i <= n; i++) {//尝试第一行的每个位置
		if (!row[x] && !col[i] && !eye1[x + n - i] && !eye2[x + i]) {
			row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 1;
			s += i + '0';
			dfs12501(x + 1, s);//x行有了皇后 继续到下一行
			s.erase(s.end() - 1);
			row[x] = col[i] = eye1[x + n - i] = eye2[x + i] = 0;//回溯
		}
	}
}

int main() {
	while (cin >> b) {
		res = 0; string s; v.clear();
		dfs12501(1, s);
		sort(v.begin(), v.end());
		cout << v[b - 1] << endl;
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")