C语言-回溯例1

               回溯法解N皇后问题 

 1,代码分析:

使用一个一维数组表示皇后的位置 

 其中数组的下标表示皇后所在的行 

数组元素的值表示皇后所在的列 

 这样设计的棋盘,所有皇后必定不在同一行 

 假设前n-1行的皇后已经按照规则排列好 

 那么可以使用回溯法逐个试出第n行皇后的合法位置 

所有皇后的初始位置都是第1列 

 那么逐个尝试就是从1试到N  

 如果当前行的皇后的位置还是在1到N的合法范围内 

那么首先要判断该行的皇后是否与前几行的皇后互相冲突 

 如果冲突,该行的皇后的位置加1,继续尝试 

如果不冲突,判断下一行的皇后 

 如果已经是最后一行,说明已经找到一个解,输出这个解 

 然后最后一行的皇后的位置加1,继续尝试下一个解 

2,代码实现:

C语言-回溯例1
 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 }
C语言-回溯例1


运行结果:

C语言-回溯例1

3,代码实现:

C语言-回溯例1
 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 }
C语言-回溯例1

运行结果:

C语言-回溯例1

C语言-回溯例1,布布扣,bubuko.com

C语言-回溯例1

上一篇:python安装zlib一直无效


下一篇:学习 C++,关键是要理解概念,而不应过于深究语言的技术细节