八皇后问题

1.生成器的回溯

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

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

图和树

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

• http://mathworld.wolfram.com/Graph.html
• http://mathworld.wolfram.com/Tree.html
• www.nist.gov/dads/HTML/tree.html
• www.nist.gov/dads/HTML/graph.html

通过在网上搜索或者浏览维基百科（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循环来实现，必须知道有多少层。如果无法知道，可使用递归。

2.问题

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

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

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

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

3.状态表示

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

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

4.检测冲突

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

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

abs(state[i]-next_x)in(0, next_y-i)

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

5.基线条件

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

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

这段代码的意思是，如果只剩下最后一个皇后没有放好，就遍历所有可能的位置，并返回那些不会引发冲突的位置。参数num为皇后总数，而参数state为一个元组，包含已经放好的皇后的位置。

6.递归条件

现在来看看这个解决方案的递归部分。处理好基线条件后，可在递归条件中假设来自更低层级（编号更大的皇后）的结果都是正确的。因此，只需在函数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部分与前面相同，因此可以稍微简化一下代码。另外，还可给参数指定默认值。

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

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

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

7.扫尾工作

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

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

因为开学比较繁忙，需要安装这学期要用的各种软件，同时也免不了一些作业（都是手写的，我搞不懂这有什么意义，搞那些东西还不如交一个程序证明你懂上课所讲的内容），今天的文章也因为这个来不及排版了，将就看吧。