Python基础教程 基线条件

9.8.5 基线条件

八皇后问题解决起来有点棘手，但通过使用生成器并不太难。然而，如果你不熟悉递归，就很难自己想出这里的解决方案。另外，这个解决方案的效率不是特别高，因此皇后非常多时，其速度可能有点慢。

下面先来看基线条件：最后一个皇后。对于这个皇后，你想如何处理呢？假设你想找出所有可能的解——给定其他皇后的位置，可将这个皇后放在什么位置（可能什么位置都不行）？可以这样编写代码。

def queens(num, state):

if len(state) == num-1:

for pos in range(num):

if not conflict(state, pos):

yield pos

这段代码的意思是，如果只剩下最后一个皇后没有放好，就遍历所有可能的位置，并返回那些不会引发冲突的位置。参数num为皇后总数，而参数state是一个元组，包含已放好的皇后的位置。例如，假设总共有4个皇后，而前3个皇后的位置分别为1、 3和0，如图9-1所示。（现在不用关心白色的皇后。）

图9-1 在一个4行4列的棋盘上放置4个皇后

从该图可知，每个皇后都占据一行，而皇后的位置是从0开始编号的（Python中通常如此）。

>>> list(queens(4, (1, 3, 0)))

[2]

代码的效果很好。这里使用list旨在让生成器生成所有的值。在这个示例中，只有一个位置符合条件。在图9-1中，在这个位置放置了一个白色皇后。（请注意，颜色没有什么特殊含义，不是程序的一部分。）