n皇后问题

在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。


典型的回溯法问题


思路:


尝试性的放置 ,从第一行开始,接着在下一行放置,(这里的好处就是不需要考虑行了,只需要考虑列和对角线)

一直纠结第一行的问题,代码中直接传参数为0,一直好奇如何控制第一行的列的变化,后来将0自己模拟走了一遍才明白。

注意判断的是否符合规则的公式:(列==列)(abs(列-列)==abs(行-行))

具体细节见注释(仔细阅读,一定能看懂,)

#include<iostream>
#include <math.h>
#define N 8
using namespace std;

int num=0;//用来记录总的放置个数
int cur[8];//此全局变量是用来记录第i行放在得第j列,其中下标为i,值为j
int check(int n){//传进来行
for(int i=0;i<n;i++){
if(cur[i]==cur[n]||abs(n-i)==abs(cur[n]-cur[i])){//判断当前放置的位置是否与之前的放置位置是否在同一列或同斜列
return 0;
}
}
return 1;
}
void putQueen(int n){
if(n==N){//如果找到了最后一行的下一行,那么就可以将次数+1了(就是之前把所有的行已经放完了,数组下标从0开始的勿忘)
num++;
}else{
for(int j=0;j<N;j++){//列的位置从0往最后放置
cur[n]=j;//记录下当前行的当前列
if(check(n)){//判断当前放置的行列是否合适
putQueen(n+1);//开始进行下一行的放置
}
}
}

}
int main(){
putQueen(0);
cout<<num;
return 0;
}

作者:半夏的故事
链接:https://juejin.cn/post/7025241982951768094
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

0 个评论

要回复文章请先登录注册