hdu 2553 N皇后问题（经典搜索+回溯）

hdu 2553 N皇后问题（经典搜索+回溯）

原题

Problem Description 在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input 共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input 1 8 5 0

Sample Output 1 92 10

思路

使用一维数组arr[i]=k，代表第i行第k个位置有皇后，只需判断这一列或斜线上是否有皇后即可，之后依次搜索回溯。

代码

#include<iostream> #include<cmath> using namespace std; int n,mun; int arr[12],brr[12]; int inspect(int k){//检查列和斜线上是否有皇后 for(int i=1;i<k;i++){ if(arr[k]==arr[i]||abs(arr[k]-arr[i])==abs(k-i)) //取绝对值 return 0; } return 1; } void dfs(int count){ if(count>n) mun++; for(int i=1;i<=n;i++){//回溯搜索 arr[count]=i; if(inspect(count)) dfs(count+1); } return ; } int main(){ for(int i=1;i<=10;i++){//打表，不然会超时 n=i; mun=0;//置零重新计数 dfs(1); brr[i]=mun; } int m; while(cin>>m&&m){ cout<<brr[m]<<endl; } return 0; }

总结

使用一维数组方便，清晰，检查是也更容易。