HDU 2553 n皇後問題（回溯）

本題用回溯法求解（采用邊生成邊檢查的方式），當不滿足條件時目前路徑不再繼續向下搜尋，而繼續另外路徑的搜尋（這樣就不會枚舉所有的）。

通過逐行向下判斷（每行一個皇後），每行都嘗試将皇後放在不同的列，然後判斷其是否滿足條件（同一列、同一對角線不能有兩個以上的皇後）

此題n<=10，測試資料中會有大量重複資料，是以要儲存答案，遇到曾經計算過的n直接輸出即可，否則可能會逾時。

#include<cstdio>
#include<cstring>
const int maxn=10;
int vis[3][maxn*2];
int ans[11];
int n;
int tol;
void search(int cur)
{
	if(cur==n){
	tol++;
	return ;
	}
	else for(int i=0;i<n;i++){
		if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){ //同一列i相同，同一對角線cur+i、cur-i+n相同（因為cur-i可能小于0，故加上n)
			vis[0][i]=vis[1][i+cur]=vis[2][cur-i+n]=1;
			search(cur+1);
			vis[0][i]=vis[1][i+cur]=vis[2][cur-i+n]=0;        //一定要改回
		}
	}
}
int main(){
	for(int i=0;i<10;i++){
    	memset(vis,0,sizeof(vis));
		tol=0;
		n=i+1;
		search(0);
		ans[i]=tol;
	}
	while(scanf("%d",&n)==1&&n){
	printf("%d\n",ans[n-1]);
	}
	return 0;
}