问题描述：
思路
如果我们是从这个n*n的棋盘中选取n个方格放皇后，再去判断是否满足条件的话，则效率会非常低，这是一个组合数 ∁ \complement ∁ n n ∗ n n \atop n*n n∗nn，当n等于8时，就要枚举次
方法一：递归暴力法
做这个题之前，我们回想一下字符串全排列，这个和它相似，可以枚举每一行的列数，枚举完一个棋盘后，判断任意两个皇后是否在同一条线上，例如上面的摆法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; } 方法二：递归回溯法
代码
#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/232910.html原文链接：https://javaforall.net
