1214：八皇后
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 9918 通过数: 6127
【题目描述】
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2…b8a=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
【分析】
显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同;如果在同列上，则列号相同;如果同在 / 斜线上，则行列值之和相同；如果同在 \ 斜线上，则行列值之差相同；从下图可验证。
考虑每行有且仅有一个皇后，设一维数组 a[1…8] 表示皇后的放置∶第 i 行皇后放在第 j 列，
用 a[i] = j 来表示，即下标是行数，内容是列数。例如∶a[3] = 5 就表示第3个皇后在第3行第5列上。
判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组 b[1…8] 控制
同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组 c[1…16]、d[-7…7]控制同一对角线上只能有一个皇后。如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下，要表示两个皇后 i 和 i 不在同一列或斜线上的条件可以描述为∶(a[i]!=a[j]) && (abs(i-j) != abs(a[i]-a[j])) { i 和 j 分别表示两个皇后的行号 }。
【参考代码】
#include <stdio.h>
#include <math.h>
#define N 9
int a[N]; //皇后放置数组
int b[N]; //标志数组，控制同一列只有一个皇后
int c[N]; //标志数组，控制正向对角线只能有一个皇后
int d[N]; //标志数组，控制反向对角线只能有一个皇后
int sum,x;
void print()
{
int i;
sum++; //方案数累加1
if(x==sum)
{
for(i=1;i<=8;i++)
printf("%d",a[i]);
printf("\n");
}
}
void dfs(int i)
{
int j;
for(j=1;j<=8;j++) // 每个皇后都有8位置（列）可以试放
{
if(!b[j] && !c[i+j] && !d[i-j+7]) //寻找放置皇后的位置
{ //由于C++不能操作负数组，因此考虑加7
a[i]=j; //摆放皇后
b[j]=1; //宣布占领第j列
c[i+j]=1; //占领两个对角线
d[i-j+7]=1;
if(i==8) //8个皇后都放好，输出
print();
else //继续递归放置下一个皇后
dfs(i+1);
b[j]=0; //递归返回，即为回溯一步，当前皇后退出
c[i+j]=0;
d[i-j+7]=0;
}
}
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
x=0;
scanf("%d",&x);
dfs(1); //从第一个皇后开始放置
sum=0;
}
return 0;
}