Python玩转游戏之八皇后问题

八皇后问题,是一个古老而著名的问题,是经典又脍炙人口的典型编程问题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

下图是八皇后问题的一个解:

这样的问题很有趣,我们还可以推广到n皇后问题。

首先定义一个冲突函数,如下,ps是positions 的缩写,表示之前摆放的皇后位置,是一个list,每个元素代表第几列放的,比如上图所有的皇后可以表示为

对吧。pos表示新皇后要放的位置,conflict函数就是检测新皇后放的位置和之前的皇后在位置上是否有冲突,有的话返回True

下面考虑一下栈应该放什么,和走迷宫问题一样,元素第一个是位置,第二个是为探查的位置。

再定义一个mou函数,因为我们知道栈的每一个元素的第一个表示位置,mou就是把位置给提取出来。很简单的。

下面就是Queen函数了,可以推广到num皇后问题的那种

更神奇的是如果你把yield ps改成print(ps)会马上打印出所有结果。

queue(8)生成的迭代器返回的部分结果如下

光分析这些数字是很抽象的,更重要的是要画出来,把问题可视化

最后

搜索完毕

确实有92个解,说明这个解法是正确的(调试出来的,哈哈哈)。

当然,令人叹为观止的是,这个问题递归也可以,而且代码看起来更简洁:

我曾经不知道这一个代码,看了又看,写了又写,代码就像魔咒一样的晦涩难懂,每次好像都若有所悟,但是忍不住又说一句,这个代码真的抽象!

(完)

看完本文有收获?请转发分享给更多人

关注「Python那些事」,做全栈开发工程师

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181026B0CJ3D00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券