QQ登录

只需一步,快速开始

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

主题

帖子

荣誉

实习版主

Rank: 10Rank: 10

技术值
查看: 1468|回复: 15

[技术交流] 三种不同算法求解八皇后问题:排列组合、回溯法+递归、生成器+递归

[复制链接]
最佳答案
57 
累计签到:365 天
连续签到:1 天
jerryxjr1220 发表于 2017-1-5 09:35:37 146815 | 显示全部楼层 |阅读模式

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

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

x
一. 八皇后问题的定义:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。

该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:

在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

二. 八皇后问题的引申 -- N皇后问题:

当n x n格的棋盘上摆放n个皇后,使其相互不能攻击,则此问题转化为n皇后问题。

显然n = 1,2,3都无解,所以n>=4。

三. 解法一: 排列组合:

当n值=4时,由排列组合C(4*4,4) = 1820 种不同排列 (算法为:math.factorial(16)/math.factorial(4)/math.factorial(16-4) = 1820,下同)
当n值=5时,由排列组合C(5*5,5) = 53130 种不同排列
当n值=6时,由排列组合C(6*6,6) = 1947792 种不同排列
当n值=7时,由排列组合C(7*7,7) = 85900584 种不同排列
当n值=8时,由排列组合C(8*8,8) = 4426165368 种不同排列

依据我们目前使用的家用型计算机,当n<7时,还勉强可以计算一下,当n>=7 时,基本上就等不起了,耗时非常长。

不过排列组合的解法是最通俗易懂,也是最简单暴力的方法,程序就不多做说明了,直接看源代码就好了:
  1. import itertools as it
  2. n = 6
  3. blank = n*n
  4. chest = [[0]*n for i in range(n)]
  5. comb = it.combinations(list(range(blank)),n)

  6. def check(x,y):
  7.         if max(chest[x]) == 1:
  8.                 return False
  9.         if max([chest[i][y] for i in range(n)]) == 1:
  10.                 return False
  11.         for i in range(n):
  12.                 for j in range(n):
  13.                         if i+j == x+y or i-j == x-y:
  14.                                 if chest[i][j] == 1:
  15.                                         return False
  16.         return True

  17. queen = 0
  18. c = 0
  19. for each in comb:
  20.         for e in each:
  21.                 x = e//n
  22.                 y = e%n
  23.                 if check(x,y):
  24.                         chest[x][y] = 1
  25.                         queen += 1
  26.                 else:
  27.                         chest = [[0]*n for i in range(n)]
  28.                         queen = 0
  29.                         break
  30.         if queen == n:
  31.                 c += 1
  32.                 print ('Solution %d:' % c)
  33.                 for q in chest:
  34.                         print (q)
  35.                 print ('*'*20)
  36.                 chest = [[0]*n for i in range(n)]
  37.                 queen = 0
复制代码

输出:
n = 6时的解:
Solution 1:
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
********************
Solution 2:
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
********************
Solution 3:
[0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
********************
Solution 4:
[0, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0]
********************
[Finished in 36.1s]

可以看到,当n=6时,用时已经需要36秒以上了。

四. 解法二:回溯法+递归:

解题的思路已经写在注释里了,直接读源代码吧。

源代码:
游客,如果您要查看本帖隐藏内容请回复


当n=8时(八皇后),输出:
Solution 1:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 2:
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

中间省略N个解

Solution 91:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 92:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

Total Solution 92, done!
[Finished in 4.0s]

可以看到,用时已经非常短了。

五. 解法三:生成器+递归:

解法三的算法不是我写出来的,我是参考了网上的达人的方法,用了生成器的方法,这样使得程序更简短、效率更高、更符合python的理念。

源代码:
游客,如果您要查看本帖隐藏内容请回复


当n=8时,输出:

省略前面若干解


Solution 91:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

Solution 92:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]

[Finished in 0.3s]
看到耗时只有0.3s,比我的递归解法缩短了10多倍的时间,而且程序不过短短二十多行代码,不愧是达人啊!
楼层
跳转到指定楼层
最佳答案
0 

尚未签到

hvagab 发表于 2017-1-9 10:32:53 | 显示全部楼层
我来学习
最佳答案
0 
累计签到:38 天
连续签到:1 天
西瓜小刚 发表于 2017-1-11 22:19:36 From FishC Mobile | 显示全部楼层
谢谢楼主分享 学习学习
最佳答案
0 
累计签到:10 天
连续签到:1 天
呵呵哒123 发表于 2017-2-25 22:58:15 | 显示全部楼层
好好看看代码
最佳答案
0 

尚未签到

岁月依旧 发表于 2017-2-26 00:06:09 | 显示全部楼层
我也学学
最佳答案
0 

尚未签到

wo4wangle 发表于 2017-2-26 11:43:21 | 显示全部楼层
!!!!!!!!!!!!!!!!
最佳答案
0 
累计签到:2 天
连续签到:2 天
jikecoder 发表于 2017-4-7 12:44:14 | 显示全部楼层
回复
最佳答案
0 

尚未签到

YURiCa 发表于 2017-4-7 14:46:36 | 显示全部楼层
学习学习
最佳答案
0 
累计签到:13 天
连续签到:1 天
luohaoyan 发表于 2017-12-9 13:31:45 | 显示全部楼层
最佳答案
0 

尚未签到

DHP 发表于 2017-12-21 22:19:58 | 显示全部楼层
最佳答案
0 

尚未签到

HelloNewWorld 发表于 2018-1-1 11:46:47 | 显示全部楼层
谢谢分享
最佳答案
0 
累计签到:19 天
连续签到:1 天
weisuo 发表于 2018-1-1 17:49:58 | 显示全部楼层
sfdfgdfh
最佳答案
0 
累计签到:1 天
连续签到:1 天
fightingzjf 发表于 2018-1-3 18:18:12 From FishC Mobile | 显示全部楼层
学习学习
最佳答案
0 
累计签到:7 天
连续签到:1 天
Justin_u 发表于 7 天前 From FishC Mobile | 显示全部楼层
。。。。。
最佳答案
0 
累计签到:7 天
连续签到:1 天
Justin_u 发表于 7 天前 From FishC Mobile | 显示全部楼层
。。。。。。
最佳答案
282 
累计签到:289 天
连续签到:3 天
新手·ing 发表于 3 天前 | 显示全部楼层
看看

发表回复

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

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /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-1-23 01:46

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