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

分析與解答

我們可以讓皇后從第一行放到第n行，我們用數組x[a]=i來表示第a個皇后的位置在第a行第i列，這樣在每次判斷是否滿足情況時我們不用去判斷是否皇后在相同行，我們只用判斷之前的1到a-1個皇后的位置和當前第a個皇后的位置是否屬于同一列或者斜線，判斷是否同一列，就判斷x[a]是否等于x[i];判斷是否同一斜線，就判斷行之差是否等于列之差也就是abs(x[k]-x[i])||x[k]==x[i]。
我們寫dfs，如果當前皇后數量超過了n，那就增加sum的個數，然后停止調用，如果沒超過n，那就要假設在第一列至第n列，如果滿足條件，就繼續調用放下一個皇后的位置，main里調用dfs（1）
代碼參考https://blog.csdn.net/u014492609/article/details/38534625

#include<cstdio> #include<cmath> using namespace std; int x[15],y[15]={0}; int sum,n; int place (int k){for(int i=1;i<k;++i)if(abs(k-i)==abs(x[k]-x[i])||x[k]==x[i])return 0;return 1; } void dfs(int a){int i;if(a>n) sum++;else {for(i=1;i<=n;++i){x[a]=i;if(place(a)) dfs(a+1);}} } int main(){int i,j,n1;for(i=1;i<=10;++i){n=i;sum=0;dfs(1);y[i]=sum;}while(scanf("%d",&n1)==1&&n1)printf("%d\n",y[n1]); }

總結

以上是生活随笔為你收集整理的（DFS）n皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。