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;
}

总结

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