QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

管理团队

Rank: 30Rank: 30Rank: 30Rank: 30

技术值
查看: 828|回复: 14

[学习笔记] ★ 第三十四讲 八皇后问题 | 【递归版】 ★

[复制链接]
最佳答案
105 
累计签到:569 天
连续签到:97 天
不二如是 发表于 2017-10-23 14:24:56 82814 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 不二如是 于 2017-10-23 14:26 编辑


                               
登录/注册后可看大图


    


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

------小甲鱼


欢乐傻笑并存

智慧邪恶同在


笔记内涵------





八皇后问题


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

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

Snip20171023_125.png


该问题是十九世纪著名的数学家高斯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. int count = 0;

  3. int notDanger( int row, int j, int (*chess)[8] )
  4. {
  5.         int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;

  6.         // 判断列方向
  7.         for( i=0; i < 8; i++ )
  8.         {
  9.                 if( *(*(chess+i)+j) != 0 )
  10.                 {
  11.                         flag1 = 1;
  12.                         break;
  13.                 }
  14.         }

  15.         // 判断左上方
  16.         for( i=row, k=j; i>=0 && k>=0; i--, k-- )
  17.         {
  18.                 if( *(*(chess+i)+k) != 0 )
  19.                 {
  20.                         flag2 = 1;
  21.                         break;
  22.                 }
  23.         }

  24.         // 判断右下方
  25.         for( i=row, k=j; i<8 && k<8; i++, k++ )
  26.         {
  27.                 if( *(*(chess+i)+k) != 0 )
  28.                 {
  29.                         flag3 = 1;
  30.                         break;
  31.                 }
  32.         }

  33.         // 判断右上方
  34.         for( i=row, k=j; i>=0 && k<8; i--, k++ )
  35.         {
  36.                 if( *(*(chess+i)+k) != 0 )
  37.                 {
  38.                         flag4 = 1;
  39.                         break;
  40.                 }
  41.         }

  42.         // 判断左下方
  43.         for( i=row, k=j; i<8 && k>=0; i++, k-- )
  44.         {
  45.                 if( *(*(chess+i)+k) != 0 )
  46.                 {
  47.                         flag5 = 1;
  48.                         break;
  49.                 }
  50.         }

  51.         if( flag1 || flag2 || flag3 || flag4 || flag5 )
  52.         {
  53.                 return 0;
  54.         }
  55.         else
  56.         {
  57.                 return 1;
  58.         }
  59. }

  60. // 参数row: 表示起始行
  61. // 参数n: 表示列数
  62. // 参数(*chess)[8]: 表示指向棋盘每一行的指针
  63. void EightQueen( int row, int n, int (*chess)[8] )
  64. {
  65.         int chess2[8][8], i, j;

  66.         for( i=0; i < 8; i++ )
  67.         {
  68.                 for( j=0; j < 8; j++ )
  69.                 {
  70.                         chess2[i][j] = chess[i][j];
  71.                 }
  72.         }

  73.         if( 8 == row )
  74.         {
  75.                 printf("第 %d 种\n", count+1);
  76.                 for( i=0; i < 8; i++ )
  77.                 {
  78.                         for( j=0; j < 8; j++ )
  79.                         {
  80.                                 printf("%d ", *(*(chess2+i)+j));
  81.                         }
  82.                         printf("\n");
  83.                 }
  84.                 printf("\n");
  85.                 count++;
  86.         }
  87.         else
  88.         {
  89.                 for( j=0; j < n; j++ )
  90.                 {
  91.                         if( notDanger( row, j, chess ) ) // 判断是否危险
  92.                         {
  93.                                 for( i=0; i < 8; i++ )
  94.                                 {
  95.                                         *(*(chess2+row)+i) = 0;
  96.                                 }
  97.                                
  98.                                 *(*(chess2+row)+j) = 1;

  99.                                 EightQueen( row+1, n, chess2 );
  100.                         }
  101.                 }
  102.         }
  103. }

  104. int main()
  105. {
  106.         int chess[8][8], i, j;

  107.         for( i=0; i < 8; i++ )
  108.         {
  109.                 for( j=0; j < 8; j++ )
  110.                 {
  111.                         chess[i][j] = 0;
  112.                 }
  113.         }

  114.         EightQueen( 0, 8, chess );

  115.         printf("总共有 %d 种解决方法!\n\n", count);

  116.         return 0;
  117. }
复制代码



这位鱼油,如果喜欢本系列笔记,请订阅 专辑传送门)(不喜欢更要订阅

本帖被以下淘专辑推荐:

楼层
跳转到指定楼层
最佳答案
17 
累计签到:201 天
连续签到:1 天
和vvv 发表于 2017-10-25 15:38:32 From FishC Mobile | 显示全部楼层
我不知道
最佳答案
0 

尚未签到

747321117 发表于 2017-12-28 12:30:29 | 显示全部楼层
最佳答案
2 

尚未签到

蓝色王魂 发表于 2018-1-14 09:24:57 | 显示全部楼层
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. def duijiao(x):
  8.     for i in range(8):
  9.         for j in range(i+1,8):
  10.             if abs(x[i][0]-x[j][0]) == abs(x[i][1]-x[j][1]):
  11.                 return False
  12.     else:
  13.         return True


  14. time = 0
  15. for a1 in range(8):
  16.     for a2 in range(8):
  17.         for a3 in range(8):
  18.             for a4 in range(8):
  19.                 for a5 in range(8):
  20.                     for a6 in range(8):
  21.                         for a7 in range(8):
  22.                             for a8 in range(8):
  23.                                 list1 = [a1,a2,a3,a4,a5,a6,a7,a8]
  24.                                 list2 = list(enumerate(list1))
  25.                                 if lie(list1) and duijiao(list2):
  26.                                     qipan = [[0 for i in range(8)] for j in range(8)]
  27.                                     for each in list2:
  28.                                         qipan[each[0]][each[1]]=1
  29.                                     for each in qipan:
  30.                                         print(each)
  31.                                     print('\n')
  32.                                     time += 1
  33. print('共有解 %d 个' % time)
复制代码
最佳答案
0 
累计签到:5 天
连续签到:1 天
1093331524 发表于 2018-1-17 10:48:13 From FishC Mobile | 显示全部楼层
我觉得八皇后这儿应该改为这个。
1516157248595881748820.jpg
最佳答案
0 
累计签到:5 天
连续签到:1 天
1093331524 发表于 2018-1-17 10:49:49 From FishC Mobile | 显示全部楼层
递归完成或者下一行没找成功,然后此位置为0,继续寻找此行符合条件的下一个
最佳答案
0 
累计签到:5 天
连续签到:1 天
1093331524 发表于 2018-1-17 13:34:01 From FishC Mobile | 显示全部楼层
这个一个数组也是可以充分够的。
最佳答案
0 

尚未签到

Code_mzh 发表于 2018-1-30 16:00:54 | 显示全部楼层
求助大神
最佳答案
0 

尚未签到

Code_mzh 发表于 2018-1-30 16:12:18 | 显示全部楼层
蓝色王魂 发表于 2018-1-14 09:24
c很好,我选择python

看不懂啊
最佳答案
0 

尚未签到

whalesea 发表于 2018-1-30 19:39:14 | 显示全部楼层
蓝色王魂 发表于 2018-1-14 09:24
c很好,我选择python

..试了下运行..显示“list” is not callable
那句 list2  = list(enumerate(list1))
是不是有问题?
最佳答案
0 

尚未签到

ab13402364 发表于 2018-2-1 15:11:59 | 显示全部楼层
来看看,学习学习
最佳答案
2 

尚未签到

蓝色王魂 发表于 2018-2-1 22:57:44 | 显示全部楼层
whalesea 发表于 2018-1-30 19:39
..试了下运行..显示“list” is not callable
那句 list2  = list(enumerate(list1))
是不是有问题 ...

我自己运行是没有问题的啊,你看一下是不是代码复制的时候出了什么问题
最佳答案
0 
累计签到:6 天
连续签到:1 天
圣狄雅哥 发表于 2018-2-3 21:34:17 | 显示全部楼层
本帖最后由 圣狄雅哥 于 2018-2-3 21:41 编辑
1093331524 发表于 2018-1-17 10:49
递归完成或者下一行没找成功,然后此位置为0,继续寻找此行符合条件的下一个


我试了试不行。
捕获.JPG
捕获2.JPG
最佳答案
0 
累计签到:6 天
连续签到:1 天
圣狄雅哥 发表于 2018-2-3 21:44:13 | 显示全部楼层

但是按理说chess2每个元素都被初始化为0了,就算后面不重新赋值为0也不影响啊
最佳答案
0 
累计签到:6 天
连续签到:1 天
圣狄雅哥 发表于 2018-2-4 11:11:01 From FishC Mobile | 显示全部楼层
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 );
                        }
                }

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

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /2 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2018-2-23 16:05

快速回复 返回顶部 返回列表