hdu 2553 N皇后问题（回溯法）

本文主要是介绍hdu 2553 N皇后问题（回溯法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2553

关键在于怎么判断主副对角线是否有皇后：

j表示纵坐标，i表示横坐标。（注意这不是数学中那个一般的二维坐标系）

主对角线易得出j==i，所以有 j1 - i1 == j2 - i2;

副对角线易得出 j1 + i1 ==j2 + i2；

详见代码。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=11;
int chessboard[MAXN];
int n,ans[MAXN],sum;
void solve(int cnt)
{if(cnt==n) sum++;else{for(int i=0;i<n;i++){bool p=true;chessboard[cnt]=i;for(int j=0;j<cnt;j++){if(chessboard[cnt]==chessboard[j]||cnt-chessboard[cnt]==j-chessboard[j]||chessboard[j]+j==cnt+chessboard[cnt])//判断列，主对角线，副对角线上是否有皇后{p=false;break;}}if(p)solve(cnt+1);}}
}
int main()
{for(int i=1;i<MAXN;i++)//预先求出，否则超时{n=i;sum=0;memset(chessboard,0,sizeof(chessboard));solve(0);ans[i]=sum;}while(scanf("%d",&n)!=EOF&&n){printf("%d\n",ans[n]);}return 0;
}

效率可以在提高些：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=11;
bool flag[3][MAXN*2];//用标记来记录列，主对角线，副对角线上是否有皇后
int n,ans[MAXN],sum;
void solve(int cnt)
{if(cnt==n) sum++;else{for(int i=0;i<n;i++){if(!flag[0][i]&&!flag[1][cnt+i]&&!flag[2][cnt-i+n]){flag[0][i]=flag[1][cnt+i]=flag[2][cnt-i+n]=true;solve(cnt+1);flag[0][i]=flag[1][cnt+i]=flag[2][cnt-i+n]=false;}}}
}
int main()
{for(int i=1;i<MAXN;i++){n=i;sum=0;memset(flag,0,sizeof(flag));solve(0);ans[i]=sum;}while(scanf("%d",&n)!=EOF&&n){printf("%d\n",ans[n]);}return 0;
}

嘿嘿：

#include<cstdio>
using namespace std;
int main()
{int n,ans[]={0,1,0,0,2,10,4,40,92,352,724};while(scanf("%d",&n)!=EOF,n)printf("%d\n",ans[n]);return 0;
}

这篇关于hdu 2553 N皇后问题（回溯法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---