N皇后递归代码

千公子

1. #include <iostream>
   
2. #include <cstring>
   
3. #define N 15
   
4. using namespace std;
   
5. int table[N] = {0};
   
6. int count = 0;
   
7. 
   
8. //x行， y列
   
9. bool check(int x, int y)
   
10. {
    
11.     //行不用检察
    
12.     for(int i=0; i<x; i++)
    
13.     {
    
14.         if(table[i] == y)
    
15.             return false;
    
16.         
    
17.         if(table[i]+i == x+y)
    
18.             return false;
    
19.         
    
20.         if(table[i]-i == y-x)
    
21.             return false;
    
22.     }
    
23.     return true;
    
24. }
    
25. 
    
26. void dfs(int col, int n)
    
27. {
    
28.     if(col == n)
    
29.     {
    
30.         count++;
    
31.         return;
    
32.     }
    
33.     for(int i = 0; i<n; i++)
    
34.     {
    
35.         if(check(col, i))
    
36.         {
    
37.             table[col] = i;
    
38.             dfs(col+1, n);
    
39.             //table[col] = 0;
    
40.         }
    
41.     }
    
42. }
    
43. 
    
44. int main(){
    
45.     int n;
    
46.     cin >> n;
    
47.     dfs(0, n);
    
48.     cout << count << endl;
    
49. 
    
50.     return 0;
    
51. }

复制代码