大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
问题描述：
有一个n*n的棋盘，在这个棋盘中放n个皇后，使得这n个皇后，任意两个皇后不在同一行，同一列，同一条对角线。例如，当n等于4时，有两种摆法。
输入只有一个整数n。
思路
如果我们是从这个n*n的棋盘中选取n个方格放皇后，再去判断是否满足条件的话，则效率会非常低，这是一个组合数 ∁ \complement ∁ n n ∗ n n \atop n*n n∗nn，当n等于8时，就要枚举54502232次
方法一：递归暴力法
做这个题之前，我们回想一下字符串全排列，这个和它相似，可以枚举每一行的列数，枚举完一个棋盘后，判断任意两个皇后是否在同一条线上，例如上面的摆法1(2413).这个方法的复杂度为n！
代码
#include<stdio.h>
#include<math.h>
int rank[15];//pos列i行
bool vis[15];//标记第i行是否走过
int n,cnt=0;
void dfs(int pos){
if(pos==n+1){
bool flag=true;
for(int i=1;i<=n;i++){
bool flag2=true;
for(int j=i+1;j<=n;j++){
//枚举任意两个皇后
if(abs(i-j)==abs(rank[i]-rank[j])){
//两个皇后处于一条对角线
flag=false;
flag2=false;
break;
}
}
if(flag2==false) break;//如果一个填满情况对角线有两个或以上，则直接跳出循环
}
if(flag) cnt++;
return;
}
for(int i=1;i<=n;i++){
//枚举每一行
if(vis[i]==false){
//第i行没走过
rank[pos]=i;//pos列在i行
vis[i]=true;
dfs(pos+1);//递归下一列
vis[i]=false;
}
}
}
int main(){
scanf("%d",&n);
dfs(1);//从第一列开始枚举
printf("%d",cnt);
return 0;
}
方法二：递归回溯法
上面的方法一是当形成一个n*n的棋盘时，才去判断是否满足条件。
而我们在递归时，可以提前判断是否满足条件，如果不满足，则不用递归下去，返回上一层进行处理，这种方法称为回溯法。这个题是当我们递归的时候就去判断当前的皇后是否和前面的皇后在一条对角线上，如果在一条直线上，就不需要递归下去了，返回上一层；如果不在，就继续递归，下一个继续进行判断，直到满足条件为止。
代码
#include<stdio.h>
#include<math.h>
int rank[20];
bool vis[20];
int n,cnt=0;
void dfs(int pos){
if(pos==n+1){
//递归边界条件
cnt++;
return;
}
for(int i=1;i<=n;i++){
//枚举每行
if(vis[i]==false){
bool flag=true;
for(int j=1;j<pos;j++){
//枚举pos之前的皇后
if(abs(pos-j)==abs(i-rank[j])){
flag=false;
break;
}
}
if(flag){
rank[pos]=i;//pos列在i行
vis[i]=true;
dfs(pos+1);
vis[i]=false;
}
}
}
}
int main(){
scanf("%d",&n);
dfs(1);
printf("%d",cnt);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/187628.html原文链接：https://javaforall.net
