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那些事」，做全栈开发工程师