N皇后问题：使用Python生成器实现的回溯解法

Question

这个生成器是怎么工作的呢？很明显，它在外层的循环中发生了变化。这个生成器是在循环过程中进行计算的吗？

这段代码是从 http://rosettacode.org/wiki/N-queens_problem#Python 适配过来的。
如果我导入这段代码，它会显示：
[[1, 3, 0, 2], [2, 0, 3, 1]]

在代码之前，它提到：
“对上面的代码做一个出人意料的简单修改（把列表推导式改成生成器表达式），就能得到一个回溯的解决方案。”

class Solution:
    # @return a list of lists of string
    def under_attack(self, col, queens):
        return col in queens or any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))

    def solve(self,n):
        solutions = [[]]
        for row in range(n):
            solutions = (solution+[i] for solution in solutions
                                      for i in range(n)    
                                      if not self.under_attack(i, solution))
        print(list(solutions))
        return solutions


A=Solution()
list(A.solve(4))

Answer 1

这个算法的工作方式和使用列表推导的算法完全一样，唯一的区别是它使用了一个生成器表达式——实际上，它创建了一个里面嵌套了更多生成器的生成器！所以，它不是一次性列出所有可能的解决方案，而是根据需要懒懒地生成更多的解决方案。

你可以通过每次调用under_attack函数时增加一个全局定义的计数器变量，来轻松验证这一点，看看这个计数器增加了多少次。

gen = solve(8) # just create the generators, under_attack called 0 times
next(gen)      # first solution,             under_attack called 876 times
list(gen)      # all remaining solutions,    under_attack called 15720

如果你执行list(gen)，它会生成所有的解决方案，而next(gen)只计算一个。

---

现在来讲讲实际的算法。用非生成器版本来解释会更简单。而且不需要类。

def under_attack(col, queens):
    return col in queens or any(abs(col - x) == len(queens)-i         # (1)
                                for i,x in enumerate(queens))         # (2)

def solve(n):
    solutions = [[]]
    for row in range(n):                                              # (3)
        solutions = [solution+[i] for solution in solutions           # (4)
                                  for i in range(n)                   # (5)
                                  if not under_attack(i, solution)]   # (6)
        print solutions # remove this when using generator!           # (7)
    return solutions

首先是under_attack函数。给定一个皇后的列和已经放置的皇后的列，这个函数检查是否在同一列已经有皇后（1，在or之前），或者是否有任何皇后在同一对角线上（2）。

接下来是solve：这个函数遍历棋盘的所有行，在每一行放置一个皇后。solutions是一个部分解决方案的列表，每个子列表保存到目前为止放置的皇后的列。[[3,1]]意味着有一个（部分）解决方案，第一行的皇后在第3列，第二行的皇后在第1列。现在，对于每一行（3），它会更新部分解决方案，结合到目前为止的每个部分解决方案（4）和新皇后的列（5），确保这个皇后不会被攻击（6）。

我选择用非生成器版本来解释的原因是，这样我们可以在每次循环迭代中打印部分解决方案（7）。如果使用生成器，这样做就不可能，因为直接打印列表会使生成器“耗尽”，之后就没有更多的部分解决方案可以继续构建了。对于n=4：

[[0],            [1],          [2],         [3]]               # 1st queen 
[[0, 2], [0, 3], [1, 3],       [2, 0],      [3, 0], [3, 1]]    # 2nd queen 
[[0, 3, 1],      [1, 3, 0],    [2, 0, 3],   [3, 0, 2]]         # 3rd queen 
[                [1, 3, 0, 2], [2, 0, 3, 1]]                   # 4th queen 

第一个皇后可以放在任何一列。这已经限制了第二个皇后的可能位置，现在只有一到两个可能的地方。第三个皇后的选择更少，对于某些情况下的第一个和第二个皇后，甚至找不到位置。最后，放置最后一个皇后，这就是解决方案集。