经典回溯问题--八皇后dfs递归回溯求解

 1 //N皇后问题 
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define N 8//皇后个数 
 8 int ans=0;
 9 int a[N]={0};//a[i]=j表示在第i行的第j列放置 
10 bool check0(int i,int j,int a_i,int a_j){//判断两个位置是否相邻，相邻则返回true ，因为是按行排列的  所以不用考虑同行的情况
11     if(a_i==a_j) return true;//放在同一列
12     if(fabs(j-i)==fabs(a_i-a_j)) return true;//放在同对角线（主对角线or次对角线）
13     return false; 
14 }
15 bool check(int i,int j){//判断a[i]=j是否不和前面几行冲突 
16     for(int k=0;k<i;k++){
17         if(check0(k,i,a[k],j))
18         return true;
19     }
20     return false;//不冲突 可以放 
21 }
22 void dfs(int n){//确定第n行应填的位置 
23     if(n==N) {
24         ans++;
25         printf("a[]: ");
26         for(int i=0;i<N;i++){
27             printf("%d ",a[i]);
28         }
29         printf("\n");
30         return;
31     }
32     for(int i=0;i<N;i++){//从第0列开始试探
33         a[n]=i;//假设放在第i列 
34         if(check(n,i)) continue;
35         dfs(n+1);
36         
37         
38     }
39 }
40 int main(){
41     dfs(0);
42     printf("共有%d种解法\n",ans);
43     return 0;
44 }