★ 第三十四讲 八皇后问题 | 【递归版】 ★

不二如是

                               
登录/注册后可看大图

  

索引帖

  

用一节课的时间，提高生活幸福感

------小甲鱼

欢乐与傻笑并存

智慧与邪恶同在

笔记内涵------

---

八皇后问题

八皇后问题，是一个古老而著名的问题。

是回溯算法的典型例题，这节课小甲鱼先用递归算法来解。

该问题是十九世纪著名的数学家高斯1850年提出：

        在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击。

        即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯先生当年由于没有学好计算机编程，没日没夜地计算呀。。。

得出结论是：

        76种硬生生把自己给“搞死”了！

对了，当年还没有计算机......

正确的结果应该是：

        92种。

本节课属于大家一起边敲代码边总结思路，所以要仔细看视频！

---

总结

第1次考虑把皇后放在第1行的某个位置。

第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。

第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。

每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。

找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。

找到一组可行解即可输出，然后程序回溯去找下一组可靠解。

我们用一个一维数组来表示相应行对应的列，比如：

1. c[i]=j//表示， 第i行的皇后放在第j列

复制代码

如果当前行是r，皇后放在哪一列呢？

答案是：

游客，如果您要查看本帖隐藏内容请回复

一共有8列，所以我们要让c[r]依次取第0列，第1列，第2列……

一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。

怎样是有冲突呢？

答案是：

        同行，同列，对角线。

由于已经不会同行了，所以不用考虑这一点。

同列：

1. c[r]==c[j];

复制代码

同对角线有两种可能，即主对角线方向和副对角线方向。

主对角线方向满足，行之差等于列之差：

1. r-j==c[r]-c[j];

复制代码

副对角线方向满足， 行之差等于列之差的相反数：

1. r-j==c[j]-c[r]；

复制代码

只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。

代码实现：

1. #include <stdio.h>
   
2. 
   
3. int count = 0;
   
4. 
   
5. int notDanger( int row, int j, int (*chess)[8] )
   
6. {
   
7.         int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;
   
8. 
   
9.         // 判断列方向
   
10.         for( i=0; i < 8; i++ )
    
11.         {
    
12.                 if( *(*(chess+i)+j) != 0 )
    
13.                 {
    
14.                         flag1 = 1;
    
15.                         break;
    
16.                 }
    
17.         }
    
18. 
    
19.         // 判断左上方
    
20.         for( i=row, k=j; i>=0 && k>=0; i--, k-- )
    
21.         {
    
22.                 if( *(*(chess+i)+k) != 0 )
    
23.                 {
    
24.                         flag2 = 1;
    
25.                         break;
    
26.                 }
    
27.         }
    
28. 
    
29.         // 判断右下方
    
30.         for( i=row, k=j; i<8 && k<8; i++, k++ )
    
31.         {
    
32.                 if( *(*(chess+i)+k) != 0 )
    
33.                 {
    
34.                         flag3 = 1;
    
35.                         break;
    
36.                 }
    
37.         }
    
38. 
    
39.         // 判断右上方
    
40.         for( i=row, k=j; i>=0 && k<8; i--, k++ )
    
41.         {
    
42.                 if( *(*(chess+i)+k) != 0 )
    
43.                 {
    
44.                         flag4 = 1;
    
45.                         break;
    
46.                 }
    
47.         }
    
48. 
    
49.         // 判断左下方
    
50.         for( i=row, k=j; i<8 && k>=0; i++, k-- )
    
51.         {
    
52.                 if( *(*(chess+i)+k) != 0 )
    
53.                 {
    
54.                         flag5 = 1;
    
55.                         break;
    
56.                 }
    
57.         }
    
58. 
    
59.         if( flag1 || flag2 || flag3 || flag4 || flag5 )
    
60.         {
    
61.                 return 0;
    
62.         }
    
63.         else
    
64.         {
    
65.                 return 1;
    
66.         }
    
67. }
    
68. 
    
69. // 参数row: 表示起始行
    
70. // 参数n: 表示列数
    
71. // 参数(*chess)[8]: 表示指向棋盘每一行的指针
    
72. void EightQueen( int row, int n, int (*chess)[8] )
    
73. {
    
74.         int chess2[8][8], i, j;
    
75. 
    
76.         for( i=0; i < 8; i++ )
    
77.         {
    
78.                 for( j=0; j < 8; j++ )
    
79.                 {
    
80.                         chess2[i][j] = chess[i][j];
    
81.                 }
    
82.         }
    
83. 
    
84.         if( 8 == row )
    
85.         {
    
86.                 printf("第 %d 种\n", count+1);
    
87.                 for( i=0; i < 8; i++ )
    
88.                 {
    
89.                         for( j=0; j < 8; j++ )
    
90.                         {
    
91.                                 printf("%d ", *(*(chess2+i)+j));
    
92.                         }
    
93.                         printf("\n");
    
94.                 }
    
95.                 printf("\n");
    
96.                 count++;
    
97.         }
    
98.         else
    
99.         {
    
100.                 for( j=0; j < n; j++ )
     
101.                 {
     
102.                         if( notDanger( row, j, chess ) ) // 判断是否危险
     
103.                         {
     
104.                                 for( i=0; i < 8; i++ )
     
105.                                 {
     
106.                                         *(*(chess2+row)+i) = 0;
     
107.                                 }
     
108.                                
     
109.                                 *(*(chess2+row)+j) = 1;
     
110. 
     
111.                                 EightQueen( row+1, n, chess2 );
     
112.                         }
     
113.                 }
     
114.         }
     
115. }
     
116. 
     
117. int main()
     
118. {
     
119.         int chess[8][8], i, j;
     
120. 
     
121.         for( i=0; i < 8; i++ )
     
122.         {
     
123.                 for( j=0; j < 8; j++ )
     
124.                 {
     
125.                         chess[i][j] = 0;
     
126.                 }
     
127.         }
     
128. 
     
129.         EightQueen( 0, 8, chess );
     
130. 
     
131.         printf("总共有 %d 种解决方法!\n\n", count);
     
132. 
     
133.         return 0;
     
134. }

复制代码

这位鱼油，如果喜欢本系列笔记，请订阅 专辑&#9758;（传送门）（不喜欢更要订阅 ）

和vvv

我不知道

747321117

蓝色王魂

c很好，我选择python

1. def lie(x):
   
2.     x.sort()
   
3.     if x == [i for i in range(8)]:
   
4.         return True
   
5.     else:
   
6.         return False
   
7. 
   
8. def duijiao(x):
   
9.     for i in range(8):
   
10.         for j in range(i+1,8):
    
11.             if abs(x[i][0]-x[j][0]) == abs(x[i][1]-x[j][1]):
    
12.                 return False
    
13.     else:
    
14.         return True
    
15. 
    
16. 
    
17. time = 0
    
18. for a1 in range(8):
    
19.     for a2 in range(8):
    
20.         for a3 in range(8):
    
21.             for a4 in range(8):
    
22.                 for a5 in range(8):
    
23.                     for a6 in range(8):
    
24.                         for a7 in range(8):
    
25.                             for a8 in range(8):
    
26.                                 list1 = [a1,a2,a3,a4,a5,a6,a7,a8]
    
27.                                 list2 = list(enumerate(list1))
    
28.                                 if lie(list1) and duijiao(list2):
    
29.                                     qipan = [[0 for i in range(8)] for j in range(8)]
    
30.                                     for each in list2:
    
31.                                         qipan[each[0]][each[1]]=1
    
32.                                     for each in qipan:
    
33.                                         print(each)
    
34.                                     print('\n')
    
35.                                     time += 1
    
36. print('共有解 %d 个' % time)

复制代码

1093331524

我觉得八皇后这儿应该改为这个。

1093331524

递归完成或者下一行没找成功，然后此位置为0，继续寻找此行符合条件的下一个

1093331524

这个一个数组也是可以充分够的。

Code_mzh

求助大神

Code_mzh

蓝色王魂 发表于 2018-1-14 09:24
c很好，我选择python

看不懂啊

whalesea

蓝色王魂 发表于 2018-1-14 09:24
c很好，我选择python

..试了下运行..显示“list” is not callable
那句 list2  = list（enumerate（list1））
是不是有问题?

ab13402364

来看看，学习学习

蓝色王魂

whalesea 发表于 2018-1-30 19:39
..试了下运行..显示“list” is not callable
那句 list2  = list（enumerate（list1））
是不是有问题 ...

我自己运行是没有问题的啊，你看一下是不是代码复制的时候出了什么问题

圣狄雅哥

1093331524 发表于 2018-1-17 10:49
递归完成或者下一行没找成功，然后此位置为0，继续寻找此行符合条件的下一个

我试了试不行。

圣狄雅哥

圣狄雅哥 发表于 2018-2-3 21:34
我试了试不行。

但是按理说chess2每个元素都被初始化为0了，就算后面不重新赋值为0也不影响啊

圣狄雅哥

for( j=0; j < n; j++ )
                {
                        if( notDanger( row, j, chess ) ) // 判断是否危险
                        {
                                for( i=0; i < 8; i++ )
                                {
                                        *(*(chess2+row)+i) = 0;
                                }
                                
                                *(*(chess2+row)+j) = 1;

                                EightQueen( row+1, n, chess2 );
                        }
                }

//这段循环与递归不是太能看懂

我要去实习！

1

lnking

mark下

赛博空间

朕想知道

lijialijialijia

谢谢

ZMichael

这怎么像是回溯方法呢？递归和回溯区别在哪？