八皇后问题--------------------递归回溯
程序员文章站
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 }
该方法其实就是穷举法,对每一种情况都进行判断,效率并不高。