八皇后问题
xixihaha2021
·
2022-08-23 15:48:39
·
个人记录
题解 八皇后问题
题意简述
综述
本题是一道搜索问题。
科普：八皇后问题是指求将八个皇后摆在一个8×8的棋盘上，要求任意两个皇后不能同行、同列、同斜线(正反斜线都不行)，求有多少种摆法。如果你对八皇后问题感兴趣，可以看看百度百科。
八皇后问题_百度百科
现在，每个人都可以在计算机的帮助下，算出八皇后问题的92组解。本题就是要我们写一个程序，输出八皇后问题的所有92组解。
描述相关
在8×8的国际棋盘上放置8个皇后，使它们互相不能一步之内(含一步)吃掉对方。
输入相关
本题无输入。
输出相关
按照如下格式依次输出八皇后问题的92组解
No. (解的编号)
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
() () () () () () () ()
棋盘中，填入0和1，0表示当前位置没有皇后，1表示当前位置有皇后。
思路简述
综述
本题可以用深度优先搜索求解。
循环92次遍历每组解法，每次输出相应组数的结果。
作者在一个很离谱的地方卡了很久——解法的顺序：每个矩阵按每行中皇后的列数输出，再转置。
深搜函数相关
每种方案的结束条件是每行都有皇后了，也就是假设要摆n个皇后，那么当当前摆的皇后数变成n+1时，方案就结束了。
方案结束后，方案数+1。如果此时的方案数和我们要求的第b个方案相等，就按题目格式输出方案。别忘了转置
对于每个对象，处理方式有n种(n=8)，判断每种处理方式是否合法，如果合法，就把当前行的皇后列数标记一下，把判断是否合法的标记也打一下，然后计算下一行。因为是深搜，为了方便计算下一种方案，计算完要把标记复原。
复杂度分析
时间复杂度分析
假设有x种方案，每种方案最差的情况下每个格子都得遍历一遍，实际上不会出现这种情况。时间复杂度为O(64×x)，即O(x)。
空间复杂度分析
本题没有用到的动态空间，故空间复杂度与代码无关，为S(1)。
代码实现
上代码！
#include
using namespace std;
int n = 8,b,a[30] = {},cnt;
bool vis[3][30];
void dfs(int x){
if(x == n + 1){
cnt++;
if(cnt == b){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++)printf("%d ",i == a[j] ? 1 : 0);
printf("\n");
}
}
return ;
}
for(int i = 1;i <= n;i++){
if(!vis[0][i] && !vis[1][x - i + n] && !vis[2][x + i]){
a[x] = i;
vis[0][i] = vis[1][x - i + n] = vis[2][x + i] = 1;
dfs(x + 1);
vis[0][i] = vis[1][x - i + n] = vis[2][x + i] = 0;
}
}
}
int main(){
for(b = 1;b <= 92;b++){
cnt = 0;
memset(vis,false,sizeof(vis));
printf("No. %d\n",b);
dfs(1);
}
return 0;
}
PS:如果哪位巨佬只想看正文，可以不看划掉的部分。