問題：n*n的棋盤上放置n個皇后，使得n個皇后不能互相攻擊（不能在同一行、同一列、同一對角線上）

思路（暴力）：枚舉1-n的全排列，判斷每個全排列是否合法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int n,count1=0;
int p[110];
bool hashTable[110]={false};
void generatep(int index)
{if(index==n+1){bool flag=true;//排列是否合法的標志for(int i=1;i<=n;i++)//枚舉任意兩個皇后{for(int j=i+1;j<=n;j++){if(abs(i-j)==abs(p[i]-p[j]))//約束條件，不在同一條對角線上flag=false;}}if(flag) count1++;return;}for(int x=1;x<=n;x++){if(hashTable[x]==false){p[index]=x;hashTable[x]=true;generatep(index+1);hashTable[x]=false;}}
}
int main()
{scanf("%d",&n);generatep(1);printf("%d",count1);return 0;
}

優化（回溯法）：當放置一部分皇后時，已經不符合，就可以不用往下遞歸
?

void generatep(int index)
{if(index==n+1)//如果到達遞歸邊界，就一定滿足條件{count1++;return;}for(int x=1;x<=n;x++){bool flag=true;if(hashTable[x]==false){for(int pre=1;pre<index;pre++)//先判斷x與之前的皇后有無沖突{if(abs(index-pre)==abs(x-p[pre])){flag=false;break;}}if(flag)//如果沒有沖突，就把x放入{p[index]=x;hashTable[x]=true;generatep(index+1);hashTable[x]=false;}}}
}

?