摘要:本文主要向大家介绍了C/C++知识点之C语言-回溯,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之C语言-回溯,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
回溯法解N皇后问题
1,代码分析:
使用一个一维数组表示皇后的位置
其中数组的下标表示皇后所在的行
数组元素的值表示皇后所在的列
这样设计的棋盘,所有皇后必定不在同一行
假设前n-1行的皇后已经按照规则排列好
那么可以使用回溯法逐个试出第n行皇后的合法位置
所有皇后的初始位置都是第1列
那么逐个尝试就是从1试到N
如果当前行的皇后的位置还是在1到N的合法范围内
那么首先要判断该行的皇后是否与前几行的皇后互相冲突
如果冲突,该行的皇后的位置加1,继续尝试
如果不冲突,判断下一行的皇后
如果已经是最后一行,说明已经找到一个解,输出这个解
然后最后一行的皇后的位置加1,继续尝试下一个解
2,代码实现:
1 /**************x皇后问题***************/
2 #include
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
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/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号