欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

八皇后问题--------------------递归回溯

程序员文章站 2022-07-02 09:39:56
1.八皇后问题 在 8×8 格的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 2.思路 这问题很适合用回溯的思想解决。首先在第一行第一列放第一个皇后,然后在第二行第一列放第二个皇后,这时对第二个皇后的列和两个斜线的方向进行判断,看是否能攻 ......

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 }

八皇后问题--------------------递归回溯

 

 该方法其实就是穷举法,对每一种情况都进行判断,效率并不高。