Python基础教程 生成器的回溯

9.8 八皇后问题

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

9.8.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 2:

...

for each possibility at level n:

is it viable?

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