鱼C论坛

 找回密码
 立即注册
查看: 13271|回复: 74

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

[复制链接]
发表于 2017-1-5 09:35:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

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多倍的时间,而且程序不过短短二十多行代码,不愧是达人啊!

评分

参与人数 1荣誉 +2 鱼币 +5 贡献 +1 收起 理由
膜法记者 + 2 + 5 + 1 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-1-9 10:32:53 | 显示全部楼层
我来学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-11 22:19:36 From FishC Mobile | 显示全部楼层
谢谢楼主分享 学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-25 22:58:15 | 显示全部楼层
好好看看代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-26 00:06:09 | 显示全部楼层
我也学学
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-26 11:43:21 | 显示全部楼层
!!!!!!!!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-7 12:44:14 | 显示全部楼层
回复
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-7 14:46:36 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-12-9 13:31:45 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-12-21 22:19:58 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-1-1 11:46:47 | 显示全部楼层
谢谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-1 17:49:58 | 显示全部楼层
sfdfgdfh
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-3 18:18:12 From FishC Mobile | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-16 17:51:56 From FishC Mobile | 显示全部楼层
。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-1-16 17:52:41 From FishC Mobile | 显示全部楼层
。。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-1-20 12:21:15 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-1-23 10:21:26 | 显示全部楼层
谢谢楼主分享 学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-1-30 14:38:01 | 显示全部楼层
好好学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-6 10:28:02 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-9 18:26:34 | 显示全部楼层
学会算法,走遍天下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 04:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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