回溯法解N皇后问题
1，代码分析：
使用一个一维数组表示皇后的位置
其中数组的下标表示皇后所在的行
数组元素的值表示皇后所在的列
这样设计的棋盘，所有皇后必定不在同一行
假设前n-1行的皇后已经按照规则排列好
那么可以使用回溯法逐个试出第n行皇后的合法位置
所有皇后的初始位置都是第1列
那么逐个尝试就是从1试到N
如果当前行的皇后的位置还是在1到N的合法范围内
那么首先要判断该行的皇后是否与前几行的皇后互相冲突
如果冲突，该行的皇后的位置加1，继续尝试
如果不冲突，判断下一行的皇后
如果已经是最后一行，说明已经找到一个解，输出这个解
然后最后一行的皇后的位置加1，继续尝试下一个解
2，代码实现：
1 /**************x皇后问题***************/ 2 #include <stdio.h> 3 #define N 4//自定义皇后的个数 4 int myabs(int a,int b) 5 { 6 return a>b?(a-b):(b-a); 7 } 8 int main() 9 { 10 int i,j,num,a[100]; 11 int k; 12 int flag;//设置标志位，用来判断是否满足约束条件 13 i=1; 14 a[1]=1;//设初值 15 num=0;//记录解得个数 16 while(1) 17 { 18 flag=1; 19 for(k=i-1;k>=1;k--) 20 { 21 if((a[k]==a[i])||myabs(a[k],a[i])==(i-k))//满足约束条件 22 flag =0;//改变标志位，表示不满足条件 23 } 24 if(flag&&(i==N))//输出一组解 25 { 26 num++; 27 for(j=1;j<=N;j++) 28 { 29 printf("%d",a[j]); 30 } 31 printf(" "); 32 if((num%8)==0) 33 { 34 printf("\n"); 35 } 36 } 37 if(flag&&i<=N) 38 { 39 i++; 40 a[i]=1;//取初值 41 continue; 42 } 43 while(a[i]==N&&i>1)i--;//回溯 44 if(a[i]==N&&i==1) 45 { 46 break; 47 } 48 else 49 { 50 a[i]++;//改变另一条路径 51 } 52 } 53 printf("\n解得个数为%d",num); 54 return 0; 55 }
运行结果：
3，代码实现：
1 /**************x皇后问题***************/ 2 #include <stdio.h> 3 #define N 8//自定义皇后的个数 4 int myabs(int a,int b) 5 { 6 return a>b?(a-b):(b-a); 7 } 8 int main() 9 { 10 int i,j,num,a[100]; 11 int k; 12 int flag;//设置标志位，用来判断是否满足约束条件 13 i=1; 14 a[1]=1;//设初值 15 num=0;//记录解得个数 16 while(1) 17 { 18 flag=1; 19 for(k=i-1;k>=1;k--) 20 { 21 if((a[k]==a[i])||myabs(a[k],a[i])==(i-k))//满足约束条件 22 flag =0;//改变标志位，表示不满足条件 23 } 24 if(flag&&(i==N))//输出一组解 25 { 26 num++; 27 for(j=1;j<=N;j++) 28 { 29 printf("%d",a[j]); 30 } 31 printf(" "); 32 if((num%8)==0) 33 { 34 printf("\n"); 35 } 36 } 37 if(flag&&i<=N) 38 { 39 i++; 40 a[i]=1;//取初值 41 continue; 42 } 43 while(a[i]==N&&i>1)i--;//回溯 44 if(a[i]==N&&i==1) 45 { 46 break; 47 } 48 else 49 { 50 a[i]++;//改变另一条路径 51 } 52 } 53 printf("\n解得个数为%d",num); 54 return 0; 55 }
运行结果：