C语言-回溯例1

浏览数：17 / 时间：2015年06月08日

回溯法解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 }