HDU 2553 n皇後問題(回溯法)，hdu2553

HDU 2553 n皇後問題(回溯法)，hdu2553

 DFS Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u  

Description

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

 

Input

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

Output

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

Sample Input

1 8 5 0  

Sample Output

1 92 10         題解：此題采用的是遞歸枚舉法（回溯法）。本題采用逐行放置。要預先把合法的放置方法數保存起來 設皇後的編號依次為1，2，……，n，則可以認為第i個皇後必須擺放在第i行，然後枚舉第一個皇後的位置進行回溯，若某一次發現某個皇後無法找到擺放位置則直接返回，如果所有皇後都可以找到擺放位置，則說明存在一種擺法滿足要求，統計有多少種擺法即可。 思路：每行最多只能有一個皇後，所以用a[ ]表示行向量，搜索從第一個行向量開始
按行向量遞增搜索，一直到最後一個行向量結束時得到一種放置方法，用b[]保存擺法。

AC代碼：

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int maxn=11;
 5 int b[maxn],a[maxn],sum,n;
 6 
 7 void dfs(int cur)
 8 {
 9     if(cur == n+1)//遞歸邊界，就有一種擺法
10         sum++;
11     else
12         for(int j = 1; j <=n; j++)
13         {
14             int ok=1;
15             a[cur] = j;//嘗試把第cur行的皇後放在第j列
16             for(int i = 1; i<cur; i++)   //檢查是否和前面的皇後沖突
17                 if(a[i] == a[cur] || abs(i - cur) == abs(a[i] - a[cur]))
18                 {
19                     ok=0;
20                     break;
21                 }
22             if(ok)
23                 dfs(cur+1);//如果合法，繼續遞歸
24         }
25 }
26 
27 int main()
28 {
29     for(int i = 1; i <=maxn; i++)
30     {
31         sum = 0;
32         n= i;
33         dfs(1);
34         b[i] = sum;
35     }
36      while(cin>>n && n)
37         cout<<b[n]<<endl;
38     return 0;
39 }

 

    一不小心找到了一個超簡單，投機取巧的方法。。。。因為n<=10。但是不能ac。

1 #include <cstdio>
2 main()
3 {
4     int n,a[13]={0,1,0,0,2,10,4,40,92,352,724,2680,14200};
5     while(scanf("%d",&n))
6         printf("%d\n",a[n]);
7 }