問題：

N皇后問題

Time Limit: 2000/1000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 21548    Accepted Submission(s): 9644

PRoblem Description在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。你的任務是，對于給定的N，求出有多少種合法的放置方法。 

Input共有若干行，每行一個正整數N≤10，表示棋盤和皇后的數量；如果N=0，表示結束。 

Output共有若干行，每行一個正整數，表示對應輸入行的皇后的不同放置數量。 

Sample Input

1850 
Sample Output
19210題解：1，逐行放置，則皇后不會橫向攻擊，因此只需檢查是否縱向和斜向攻擊即可，代碼：
#include<cstdio>#include<string.h>int c[33],tot,n;void search(int cur){	int i,j;	if(cur==n)	tot++;	else for(i=0;i<n;i++)	{		int ok=1;		c[cur]=i;		for(j=0;j<cur;j++)		if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])		{			ok=0;			break;		}		if(ok)		search(cur+1);	}}int main(){	while(scanf("%d",&n)&&n)	{	tot=0;	memset(c,0,sizeof(c));    search(0);	printf("%d/n",tot);    }	return 0;}2：提高效率：利用二維數組vis[2][]直接判斷當前嘗試的皇后所在的列和兩個對角線是否已有其他皇后。因為下標相減可能為負數，存取時要加上n.（對角線下標相加或相減相同）代碼：
#include<cstdio>#include<string.h>int n,tot,vis[3][22],c[11];void search(int cur){	int i,j;	if(cur==n)	{	tot++;	return;}	else for(i=0;i<n;i++)	{		if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])		//利用二維數組直接判斷 		{			c[cur]=i;			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=1;//修改全局變量 			search(cur+1);			vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=0;//要恢復原狀 		}	}}int main(){	while(scanf("%d",&n)&&n)	{		tot=0;		memset(c,0,sizeof(c));		memset(vis,0,sizeof(vis));		search(0);		printf("%d/n",tot);	}}但是以上代碼對于這道題依然超時！！！借鑒了別人不超時的打表做法代碼：
#include<stdio.h>#include<string.h>#include<stdlib.h>int n,ans;int map[15];int visit[15];   int sol[15];int dfs(int k){	int i,j,flag;	if(k==n+1)//  遞歸結束條件 	{		ans++;//做個說明，判斷第一列開始，那么就是從第一列的第一行查找到第五行 		return 0;	}//此種方法是按照列來存儲的，所以是從1-n來村的，就是說k是標志 	for(i=1;i<=n;i++)// 從第一行開始到第n行 	if(!visit[i])  //判斷各行是否已經有棋子 	{		map[k]=i;//如果這一行沒有棋子，則用map[k]=i來記錄，其中i為第幾行 		flag=1;// k為第幾列，則皇后存儲在第k列，第i行 		for(j=1;j<=k-1;j++) //判斷是否在同一斜線上，j從第一列開始查找到第k-1列 		if((map[k]-map[j])==(k-j)||(map[k]-map[j])==(j-k))//畫個圖驗證一下 		{			flag=0;			break;		}		if(flag)		{			visit[i]=1;			dfs(k+1);			visit[i]=0;  //釋放第i列，進行下一次搜索，此處要注意遞歸到結束的時候會返回的 		}//一步步返回到某一步，再繼續查找，這個遞歸只解釋到這里吧 	}//自己舉個9*9的例子就理解為什么了，或者6*6吧 }int main(){	int i;	for(i=1;i<=10;i++)//  先進行打表，就是先存儲，要不然會超時 	{		ans=0;//  統計方法種數 		n=i;//   因為第16步要用到n，自己粘貼到dev上看看 		memset(map,0,sizeof(map));//初始化 		memset(visit,0,sizeof(visit));		dfs(1);//   1表示從第一列開始，可以自己花一個5*5的方格 		sol[i]=ans;	}	while(scanf("%d",&n),n)	printf("%d/n",sol[n]);	return 0;}