题目描述
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。
如何将 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
思想
我们都知道八皇后复杂度是O(n^3)
多余的时间损耗都在于O(n)的更新
那么有没有可能做到O(1)的状态更新吗
首先行和列自然是很简单一个行数组和一个列数组很轻松就可以解决
然后接下来处理斜线更新就好了
但斜线有没有可能做到O(1)的更新呢
其实也是有的虽然不够那么显然
首先斜线我们都知道斜率是-1或1这样两类线
接下来描述一条线我们则有截距式公式
Y= X+b1
Y= -X+b2
那么对于棋盘中的坐标x,y
我们通过带入截距式方程轻松的就可以求出
截距的大小
所以对于同一条直线截距应该是相等并且满足截距式方程的
因此我们可以发现我们可以同x,y一样声明一个截距数组
由于-1&1是两类线段我们分成两个数组记录
那么对于点(x,y) b1 = y+x,b2 = y-x
综上所述我们判断当前点A是否可选只需要判断是否行||列||斜线可选就可以了
一个被选过则不可占用
接下来就是老生常谈的递推了
n皇后每行必然有且仅有一个皇后
因此我们选择第i行的皇后就确定了一个前i行皇后的一个集合
这里就是说每步确定一个状态后面的状态基于之前状态不会对之前状态起到影响
这里由于是列优先我就以行为基准
每行枚举选当前行每个元素的所有情况进行递推
时间复杂度
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
string s[92]={""};
void dfs(int i,bool visit[4][20],string s1){
if(i>7){
s[cnt++] =s1;
return;
}
for(int j=0;j<8;j++){
if(visit[0][i]||visit[1][j]||visit[2][i+j]||visit[3][j-i+8])
continue;
visit[0][i]=visit[1][j]=visit[2][i+j]=visit[3][j-i+8]= true;
dfs(i+1,visit,s1+char(j+'1'));
visit[0][i]=visit[1][j]=visit[2][i+j]=visit[3][j-i+8]= false;
}
};
int main(){
bool visit[4][20]={false};
string s1 = "";
dfs(0,visit,s1);
int n,num;
cin>>n;
while(n--){
cin>>num;
cout<<s[num-1]<<endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla