电脑桌面壁纸动态鱼,油嘴滑舌造句,裴勇俊爱妻生子
1.八皇后问题
在 8×8 格的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
2.思路
这问题很适合用回溯的思想解决。首先在第一行第一列放第一个皇后，然后在第二行第一列放第二个皇后，这时对第二个皇后的列和两个斜线的方向进行判断，看是否能攻击到，如果能攻击到，那就放在第二列，如果攻击不到，则继续在第三行第一列放第三个皇后，继续按照之前的的方法进行判断操作。如果放到第八个皇后
则摆法加一。这时可以回溯了，第八行的皇后改变列，看是否满足条件，满足则摆法加一，不满足，则继续改变列直到所有列都试过。当第八个皇后的所有列都试过过，继续回溯，按照之前的做法对第七个皇后进行同样的操作，直到所有皇后都回溯一遍，得到所有摆法。
3.如何判断是否攻击到
行的方向不用判断，每一行只能放一个皇后。列的方向很容易判断。对于两个斜线的方向，有一个简单有效的方法，就是判断斜率就行了。如果有多个皇后在同一个斜线上，那么他们的两个斜线的斜率为1或-1。皇后所在的列就是x值，所在的行就是y值，如果两个皇后在同一斜线上那么他们的x值之差的绝对值一定等于y值差的绝对值。
4.具体思路
棋盘一般用一个二维数组来表示，但其实可以用一个一维数组queen[8]来表示，索引表示第几个皇后也就是第几行，值表示皇后在第几列。
代码如下：
我要评论 1 #include<math.h>
2 int count=0;//计算有多少种摆法
3 //打印具体的摆法
4 void print(int * queen)
5 {
6 int i,j;
7 for(i=0;i<8;i++)
8 {
9 for(j=0;j<8;j++)
10 {
11 if(j==queen[i])
12 printf("1 ");
13 else
14 printf("0 ");
15 }
16 printf("\n");
17 }
18 printf("\n\n");
19 }
20 //判断是否满足摆放条件
21 int judge(int * queen,int n)
22 {
23 int i;
24 for(i=0;i<n;i++)
25 { //列方向 //斜线方向
26 if(queen[i]==queen[n]||abs(n-i)==abs(queen[n]-queen[i]))
27 return 0;//不满足返回0
28 }
29 return 1;//满足条件，返回1
30 }
31
32 void countqueen(int * queen,int n)
33 {
34 int i;
35 //放到第八个皇后
36 if(n==8)
37 {
38 //把摆法打印出来
39 print(queen);
40 count++;//摆法加一
41 }
42 else
43 {
44 for(i=0;i<8;i++)
45 {
46 queen[n]=i;//第n个皇后放在第i列
47 //不满足继续循环，改变位置
48 if(judge(queen,n))//如果该位置满足则放下一个皇后
49 {
50 countqueen(queen,n+1);//放下一个皇后
51 }
52 }
53 }
54 }
55 int main()
56 {
57
58 int queen[8]={0};
59 countqueen(queen,0);
60 printf("一共有 %d 种 \n",count);//打印摆法
61 return 0;
62 }
该方法其实就是穷举法，对每一种情况都进行判断，效率并不高。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论