一、八皇后
描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将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
（一）问题分析
思想：DFS通过递归地尝试所有可能的放置位置来寻找解决方案。对于每一步，它都会尝试在当前行的每一列放置皇后，并递归地检查下一行。如果成功地在所有行都放置了皇后，就找到了一个解决方案。如果某个放置导致冲突，则回溯到上一步，并尝试其他可能的放置
说明：皇后串的比较是基于整数的比较，这意味着我们可以将皇后串视为一个八位数（每位都是0到7之间的数字），并按照整数的自然顺序进行比较。在这个问题中，由于只有8行和8列，且每行只能放置一个皇后，因此解决方案的数量是有限的（92组解），这使得DFS成为了一个可行的解决方案。
步骤：
-
初始化：
（1）二维数组vis来标记棋盘上的位置是否已被占用
（2）数组b来记录每一行皇后放置的列数。
（3）二维数组a来存储所有找到的解决方案。
（4）计数器tot来记录找到的解决方案数量。 -
递归函数
dfs(step)：
（1）step表示当前正在尝试放置皇后的行数。
（2）如果step超过了8（即已经尝试完所有行），则意味着找到了一个有效的解决方案，将其保存到a数组中，并增加tot计数器。
（3）否则，对于当前行的每一列（1到8），检查是否可以在该列放置皇后：
a.递归返回后，撤销当前列的占用标记，以便尝试其他列。
b.如果没有被占用，标记这些位置为已占用，将当前列数记录到b[step]中，然后递归调用dfs(step + 1)来尝试下一行。
c.用vis数组检查当前列、当前行所在的主对角线和副对角线是否已被占用。 -
位置合理性判断
（1）列冲突（vis[0][i]）：
每一列只能有一个皇后，因此我们需要跟踪哪些列已经被占用。vis[0][i]表示第i列是否被占用。如果vis[0][i] == 0，则表示第i列是空的，可以放置皇后
（2）主对角线冲突（vis[1][step - i + 8]）：
在一个8x8的棋盘上，主对角线上的元素满足行号和列号之差为常数。例如(1,1)、(2,2)、(3,3)...(8,8)代表最长的从左上至右下的对角线。若行号和列号之差相同的位置上，均放置皇后会导致主对角线冲突。这里加8是为了避免为负数的情况
（3）副对角线冲突（vis[2][step + i]）：
在一个8x8的棋盘上，副对角线上的元素满足行号和列号之和为常数。例如(1,8)、(2,7)、(3,6)...(8,1)代表最长的从右上至左下的对角线。若行号和列号之和相同的位置上，均放置皇后会导致副对角线冲突。
（二）代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 100
using namespace std;int a[N][N], b[N];
int vis[N][N]; // 二维数组，用于标记访问状态
int tot; // 用于记录找到的有效路径数量// 深度优先搜索函数
void dfs(int step) {if (step == 9) { // 当step达到9时，表示已经找到了一个有效的路径tot++; // 有效路径数量加一for (int i = 1; i <= 8; i++) {a[tot][i] = b[i]; // 将当前路径记录到数组a中}return;}for (int i = 1; i <= 8; i++) { // 尝试每一步的8种可能（// 检查是否满足条件 if (vis[0][i] == 0 && vis[1][step + i] == 0 && vis[2][step - i + 8] == 0) {// 标记当前选择为已访问vis[0][i] = 1;vis[1][step + i] = 1;vis[2][step - i + 8] = 1;// 记录当前步的选择b[step] = i;// 递归调用dfs函数，进行下一步的选择dfs(step + 1);// 回溯，撤销当前选择vis[0][i] = 0;vis[1][step + i] = 0;vis[2][step - i + 8] = 0;}}
}int main() {int n;cin >> n; // 输入需要查询的路径数量dfs(1); // 从第一步开始深度优先搜索while (n--) { // 对每一条需要查询的路径int i;cin >> i; // 输入要查询的路径编号for (int j = 1; j <= 8; j++) { // 输出该路径的每一步选择cout << a[i][j];}cout << endl; // 输出换行符}return 0;
}
