>>> from env_helper import info; info()
页面更新时间: 2023-06-24 11:28:13
运行环境:
    Linux发行版本: Debian GNU/Linux 12 (bookworm)
    操作系统内核: Linux-6.1.0-9-amd64-x86_64-with-glibc2.36
    Python版本: 3.11.2

11.5. 八皇后问题‌求解

学习各种魔法方法后,该付诸应用了。本节将演示如何使用生成器来解决一个经典的编程 问题。

11.5.1. 生成器的回溯

对于逐步得到结果的复杂递归算法,非常适合使用生成器来实现。要在不使用生成器的情况 下实现这些算法,通常必须通过额外的参数来传递部分结果,让递归调用能够接着往下计算。通 过使用生成器,所有的递归调用都只需生成其负责部分的结果。前面的递归版flatten就是这样 做的,你可使用这种策略来遍历图结构和树结构。

然而,在有些应用程序中,你不能马上得到答案。你必须尝试多次,且在每个递归层级中都 如此。打个现实生活中的比方吧,假设你要去参加一个很重要的会议。你不知道会议在哪里召开, 但前面有两扇门,而会议室就在其中一扇门的后面。你选择进入左边那扇门后,又看到两扇门。 你再次选择进入左边那扇门,但发现走错了。因此你往回走,并进入右边那扇门,但发现也走错 了。因此你继续往回走到起点,现在可以尝试进入右边那扇门。

图和树

如果你以前从未听说过图和树,应尽快学习,因为它们是编程和计算机科学中非常重要 的概念。要深入了解图和树,可参阅计算机科学、离散数学、数据结构或算法方面的图书。 下面的网页提供了有关图和树的简明定义:

通过在网上搜索或浏览维基百科(http://wikipedia.org ),可找到大量有关这些主题的资料。

对于需要尝试所有组合直到找到答案的问题,这种回溯策略对其解决很有帮助。这种问题的 解决方案类似于下面这样:

# 伪代码
for each possibility at level 1:
    for each possibility at level 2:
        ...
            for each possibility at level n:
                is it viable?

要直接使用for循环来实现,必须知道有多少层。如果无法知道,可使用递归。

11.5.2. 问题

这是一个深受大家喜爱的计算机科学谜题:你需要将8个皇后放在棋盘上,条件是任何一个 皇后都不能威胁其他皇后,即任何两个皇后都不能吃掉对方。怎样才能做到这一点呢?应将这些 皇后放在什么地方呢?

这是一个典型的回溯问题:在棋盘的第一行尝试为第一个皇后选择一个位置,再在第二行尝 试为第二个皇后选择一个位置,依次类推。在发现无法为一个皇后选择合适的位置后,回溯到前 一个皇后,并尝试为它选择另一个位置。最后,要么尝试完所有的可能性,要么找到了答案。

在前面描述的问题中,只有8个皇后,但这里假设可以有任意数量的皇后,从而更像现实世 界的回溯问题。如何解决这个问题呢?如果你想自己试一试,就不要再往下读了,因为马上就会 提供解决方案。

注意 对于这个问题,可找到效率高得多的解决方案。如果你想深入了解,在网上搜索就可找 到大量的信息。

11.5.3. 状态表示

可简单地使用元组(或列表)来表示可能的解(或其一部分),其中每个元素表示相应行中 皇后所在的位置(即列)。因此,如果state[0] == 3,就说明第1行的皇后放在第4列(还记得吧, 我们从0开始计数)。在特定的递归层级(特定的行),你只知道上面各皇后的位置,因此状态元 组的长度小于8(即皇后总数)。

注意 完全可以使用列表(而不是元组)来表示状态,具体使用哪个完全取决于你的喜好。一 般而言,如果序列较小且是静态的,使用元组可能是不错的选择。

11.5.4. 检测冲突

先来做些简单的抽象。要找出没有冲突(即任何一个皇后都吃不到其他皇后)的位置组合, 首先必须定义冲突是什么。为何不使用一个函数来定义呢?

函数conflict接受(用状态元组表示的)既有皇后的位置,并确定下一个皇后的位置是否会 导致冲突。

>>> def conflict(state, nextX):
>>>     nextY = len(state)
>>>     for i in range(nextY):
>>>         if abs(state[i] - nextX) in (0, nextY - i):
>>>             return True
>>>     return False

参数nextX表示下一个皇后的水平位置(x坐标,即列),而nextY为下一个皇后的垂直位置(y 坐标,即行)。这个函数对既有的每个皇后执行简单的检查:如果下一个皇后与当前皇后的x坐标 相同或在同一条对角线上,将发生冲突,因此返回True;如果没有发生冲突,就返回False。比 较难理解的是下面的表达式:

abs(state[i] - nextX) in (0, nextY - i)

如果下一个皇后和当前皇后的水平距离为0(在同一列)或与它们的垂直距离相等(位于一条对角线上),这个表达式就为真;否则为假。

基线条件

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

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

>>> 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所示。(现在不用 关心白色的皇后。)

在一个4行4列的棋盘上放置4个皇后

图 11.1 在一个4行4列的棋盘上放置4个皇后

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

>>> list(queens(4, (1, 3, 0)))
[2]

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

11.5.5. 递归条件

现在来看看这个解决方案的递归部分。处理好基线条件后,可在递归条件中假设来自更低层 级(编号更大的皇后)的结果都是正确的。因此,只需在函数queens的前述实现中给if语句添加 一个else子句。

你希望递归调用返回什么样的结果呢?你希望它返回当前行下面所有皇后的位置,对吧?假 设位置是以元组的方式返回的,因此需要修改基线条件,使其返回一个(长度为1的)元组,但 这将在后面处理。

因此,对于递归调用,向它提供的是由当前行上面的皇后位置组成的元组。对于当前皇后的 每个合法位置,递归调用返回的是由下面的皇后位置组成的元组。为了让这个过程不断进行下去, 只需将当前皇后的位置插入返回的结果开头,如下所示:

...
else:
for pos in range(num):
    if not conflict(state, pos):
        for result in queens(num, state + (pos,)):
            yield (pos,) + result

这里的for pos和if not conflict部分与前面相同,因此可以稍微简化一下代码。另外,还 可给参数指定默认值。

>>> def queens(num=8, state=()):
>>>     for pos in range(num):
>>>         if not conflict(state, pos):
>>>             if len(state) == num-1:
>>>                 yield (pos,)
>>>             else:
>>>                 for result in queens(num, state + (pos,)):
>>>                     yield (pos,) + result

如果你觉得这些代码难以理解,用自己的话来描述其作用可能会有所帮助。另外,你可能还记得(pos,)中的逗号必不可少(不能仅用圆括号将pos括起),这样得到的才是元组。

生成器queens提供了所有的解(即所有合法的皇后位置组合)。

>>> list(queens(3))
[]
>>> list(queens(4))
[(1, 3, 0, 2), (2, 0, 3, 1)]
>>> for solution in queens(8):
...
print solution
...
(0, 4, 7, 5, 2, 6, 1, 3)
(0, 5, 7, 2, 6, 3, 1, 4)
...
(7, 2, 0, 5, 1, 4, 6, 3)
(7, 3, 0, 2, 5, 1, 6, 4)
>>>

如果运行queens时将参数num设置为8,将快速显示大量的解。下面看看有多少个解。

>>> len(list(queens(8)))
92

11.5.6. 扫尾工作

结束本节之前,可以让输出更容易理解些。在任何情况下,清晰的输出都是好事,因为这让查找bug等工作更容易。

>>> def prettyprint(solution):
>>>     def line(pos, length=len(solution)):
>>>         return '. ' * (pos) + 'X ' + '. ' * (length-pos-1)
>>>         for pos in solution:
>>>             print(line(pos))

请注意,我在prettyprint中创建了一个简单的辅助函数。之所以将它放在prettyprint中, 是因为我认为在其他地方都用不到它。下面随机地选择一个解,并将其打印出来,以确定它是正确的。

>>> import random
>>> prettyprint(random.choice(list(queens(8))))

. . . . . X . .

. X . . . . . .

. . . . . . X .

X . . . . . . .

. . . X . . . .

. . . . . . . X

. . . . X . . .

. . X . . . . .

下图显示了这个解。

八皇后问题的众多解之一

图 11.2 八皇后问题的众多解之一