题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。
如何将 8个皇后放在棋盘上（有 8×8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的 8皇后的摆放方法，定义一个皇后串 a与之对应，即 a=b1b2…b8，其中 bi为相应摆法中第 i行皇后所处的列数。已经知道 8皇后问题一共有 92组解（即 92个不同的皇后串）。
给出一个数 b，要求输出第 b个串。串的比较是这样的：皇后串 x置于皇后串 y之前，当且仅当将 x
视为整数时比 y小。

输入格式
第一行包含整数 n，表示共有 n组测试数据。
每组测试数据占 1行，包括一个正整数 b。

输出格式
输出有 n 行，每行输出对应一个输入。

输出应是一个正整数，是对应于 b的皇后串。

数据范围
1≤b≤92

样例

输入样例：
2
1
92
输出样例：
15863724
84136275

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int pos[93][9], c[9],zhu[20], fu[20],tmp[9];
int cnt = 1;
void dfs(int i){
    if(i == 9) {
        for(int i = 1; i <= 8; i++){
            pos[cnt][i] = tmp[i];
        }
        cnt ++;
        return;
    }

    for(int j = 1; j <= 8; j++) {
        if(c[j] || fu[i + j] || zhu[i - j  + 8]) continue;
        tmp[i] = j;
        c[j] = fu[i + j] = zhu[i - j + 8] = 1;
        dfs(i + 1);
        c[j] = fu[i + j] = zhu[i - j + 8]  = 0;
    }
}

int main(){
    int t; cin >> t;
    dfs(1);
    while(t--){
        memset(c,0,sizeof c); memset(zhu,0,sizeof zhu); memset(fu,0,sizeof fu);
        int n; cin >> n;
        for(int i = 1; i<= 8; i++){
            cout << pos[n][i];
        }
        cout << '\n';
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla