总时间限制: 2000ms 单个测试点时间限制: 500ms 内存限制: 65536kB

描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即 a=bb….b，其中b为相应摆法中第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

思路

两步走：

1. 打表：将所以92种八皇后的摆放方法求解出并保存起来；
2. 查表：按照题目要求查找输出。

从第一个皇后的位置开始尝试，如果一旦遇到某个无论如何都不能摆放的情景，那么之前已经摆放的所以皇后的位置前缀不可能使问题有解。换句话说，八皇后问题可以用一个带回溯的递归过程系统遍历所有的皇后串，得到全部的92个解。递归边界：找到了最后一个皇后的位置。

为了尽可能避免皇后相互对冲，我们规定：

1. 每行只能放1个皇后；
2. 每列只能放1个皇后。

这样我们只需要考虑斜线的皇后会不会对冲了。

如何考虑斜线的情况呢？我们可以发现，这个问题里的斜线是一条斜率为1的直线。

这意味着斜线上任意2点有:

即任意两点

代码

#include <iostream>
#include <cmath>
using namespace std;
int queen[92][8], row[8], num = 0;
void findSolution(int);
int main() {
    findSolution(0);
    int number, temp;
    cin >> number;
    for(int i = 0; i < number; i++) {
        cin >> temp;
        for(int j = 0; j < 8; j++) { // 输出第 temp 个解中皇后的列号串
            cout << queen[temp - 1][j];
        }
        cout << endl;
    }
    return 0;
}
void findSolution(int arg) {
    if( arg == 8 ) {  // 一组新的解产生了
        for(int j = 0; j < 8; j++) 
            queen[num][j] = row[j];
        num++;
        return;
    }
    // 将当前皇后逐一尝试放置在不同的列，每列对应一组解
    for(int i = 1; i <= 8; i++) {
        int j = 0;
        for(j = 0; j < arg; j++) {  // 逐一判定 arg 与前面的皇后是否对冲
            if( row[j] == i || abs( j-arg ) == abs( row[j] - i ) )
            /* 
              1. 各行的皇后都不在同一列上 
              2. 各行的皇后都不在对角线上 
            */
                break;
        }
        if(j == arg) {  // 若都不冲突
            row[j] = i; // 则重新放置新皇后
            findSolution(arg + 1); // 对下一个皇后位置进行递归
        }
    }
}