【Python】一行代码打印八皇后问题所有解

起因

群友们在群里聊天，其中一名群友在群里发了一张截图，如下：

看到 Scala 这门语言可以一行代码打印八皇后问题所有解，我想知道 Python 是否也可以。

（注1：上图中的代码不止一行，但是把换行符全部删掉依旧可以运行）

（注2：上图中的代码只能打印一种解，是因为取的 next，稍微改改就能打印所有解，无需增加行数）

问题

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，八皇后问题研究的是如何将 8 个皇后放置在 8×8 的棋盘上，并且使皇后彼此之间不能相互攻击。

解法

既然有现成的答案，咱们就在它的基础上改一改吧：

from itertools import combinations, permutations

print('\n\n'.join(['\n'.join([' '.join(['皇' if j == k else '＿' for k in range(8)]) for j in i]) for i in filter(lambda x: all([a + b != c + d and a + d != b + c for ((a, b), (c, d)) in combinations(enumerate(x), 2)]), permutations(range(8)))]))
1
2
3

输出：

皇 ＿ ＿ ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ ＿ 皇 ＿ ＿ ＿
＿ ＿ ＿ ＿ ＿ ＿ ＿ 皇
＿ ＿ ＿ ＿ ＿ 皇 ＿ ＿
＿ ＿ 皇 ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ ＿ ＿ ＿ 皇 ＿
＿ 皇 ＿ ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ 皇 ＿ ＿ ＿ ＿

皇 ＿ ＿ ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ ＿ ＿ 皇 ＿ ＿
＿ ＿ ＿ ＿ ＿ ＿ ＿ 皇
＿ ＿ 皇 ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ ＿ ＿ ＿ 皇 ＿
＿ ＿ ＿ 皇 ＿ ＿ ＿ ＿
＿ 皇 ＿ ＿ ＿ ＿ ＿ ＿
＿ ＿ ＿ ＿ 皇 ＿ ＿ ＿

省略……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（注3：itertools 是 Python 内置模块，因此忽视 import 语句的话，确实是一行）

总结

首先，生成 0 到 7 的全排列，对于全排列中的每一种排列都可看作一个有 8 个 int 类型元素的 tuple，而全排列则是该 tuple 的 list，元素的值与下标分别作为皇后们的横纵坐标，保证了皇后们在同一行与同一列上唯一。

接着，对每一种排列，将皇后们两两组合，在 lambda 函数中检测是否不处于同一条对角线上，若全部组合都通过判断则代表这是其中一种解，否则丢弃这种排列。

最后，将所有解转换成文本打印出来，非常巧妙的一种解题方法。

我们还可以拓展到 N 皇后问题，把代码中的 8 替换成 N 即可，在 N 不太大时仍然可以很好的运行，若 N 非常大，建议采用更高效的算法。