题目
总时间限制: 1000ms 内存限制: 65536kB
描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将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
题意
输入数据组数和b，输出八皇后的第b个串
思路
这题可以用深度优先搜索和递归，用数组a来表示棋盘，其中a[i][j]=1表示在第i行第j列放置了皇后。
用数组sum 来存储所有找到的解，其中 sum[k][i] 表示第k个解中第i行皇后所在的列号。
从第1行开始，逐行尝试放置皇后，对于每一行，尝试所有8个可能的列，位置对于每个位置，检查是否安全（不会被其他皇后攻击）
如果当前行找不到安全位置，则回溯到上一行，撤销上一行的皇后放置，尝试下一个可能的位置，接着继续向下搜索。
j函数检查三个方向：第y列，(x,y)位置的左上方向对角线，(x,y)位置的右上方向检查对角线。
当8个皇后全部放置，计数器ans加1，用sum数组记录每个皇后所在的列号。
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[100][100]={0},b,sum[100][100]={0},ans=0;
bool j(int x,int y){//检查函数//检查列for(int i=1;i<=8;i++){if(a[i][y]==1) return false;}//检查左上对角线for(int i=x,j=y;i>=1&&j>=1;i--,j--){if(a[i][j]==1) return false;}//检查右上对角线for(int i=x,j=y;i>=1&&j<=8;i--,j++){if(a[i][j]==1) return false;}return true;//如果所有检查都通过，说明位置安全
}
//搜索函数
void d(int x){//如果已经成功放置了8个皇后就终止if(x>8){ans++;//解的数量加1for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){if(a[i][j]==1){sum[ans][i]=j;//记录第ans个解中第i行皇后在第j列break;}}}return;//返回上一层递归}//尝试在当前行的每一列放置皇后for(int y=1;y<=8;y++){if(j(x,y)==true){//如果当前位置安全a[x][y]=1;//放置皇后d(x+1);//递归放置下一行的皇后a[x][y]=0;//撤销当前放置的皇后}}
}
int main(){cin>>n;d(1);//从第1行开始生成for(int i=1;i<=n;i++){cin>>b;//输出第b个解for(int j=1;j<=8;j++){cout<<sum[b][j];}cout<<endl;}return 0;
}