1

这个生成器是如何工作的？它显然在外部 for 循环期间发生了变化。生成器是否在 for 循环期间进行评估？

代码改编自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))
4

1 回答 1

3

该算法的工作方式与使用列表推导的算法完全相同，唯一的区别在于它使用了生成器表达式——事实上，它创建了一个包含更多生成器的生成器！因此，它不是一次列出所有可能的解决方案，而是根据需要懒惰地生成更多解决方案。

您可以通过在每次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），或者any皇后是否在同一对角线上（2）。

现在 for solve：这会遍历棋盘的所有行，每行放置一个皇后。solutions是部分解决方案的列表，其中每个子列表包含到目前为止放置的皇后的列。[[3,1]]将意味着一个（部分）解决方案在第 0 行第 3 列和第 1 行第 1 列中有一个女王。现在，对于每一行（3），它使用行的部分解决方案的每个组合更新部分解决方案，所以far ( 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

第一个皇后可以放在任何一列。这已经限制了第二个女王的可能位置，现在只有一两个可能的位置。第三个皇后更受限制，对于皇后1和2的某些位置，根本找不到位置。最后，放置最后一个皇后，这就是解决方案集。

于 2014-07-31T08:49:54.530 回答