如何从递归回溯算法中收集和返回解决方案，而不是打印它们？

Question

我为N皇后问题编写了Python代码，它会在找到每个解时将其打印出来。

def solve(n):
    #prepare a board
    board = [[0 for x in range(n)] for x in range(n)]
    #set initial positions
    place_queen(board, 0, 0)
    
def place_queen(board, row, column):
    """place a queen that satisfies all the conditions"""
    #base case
    if row > len(board)-1:
        print board
    #check every column of the current row if its safe to place a queen
    while column < len(board):
        if is_safe(board, row, column):
            #place a queen
            board[row][column] = 1
            #place the next queen with an updated board
            return place_queen(board, row+1, 0)
        else:
            column += 1
    #there is no column that satisfies the conditions. Backtrack
    for c in range(len(board)):
        if board[row-1][c] == 1:
            #remove this queen
            board[row-1][c] = 0
            #go back to the previous row and start from the last unchecked column
            return place_queen(board, row-1, c+1)
        
def is_safe(board, row, column):
    """ if no other queens threaten a queen at (row, queen) return True """
    queens = []
    for r in range(len(board)):
        for c in range(len(board)):
            if board[r][c] == 1:
                queen = (r,c)
                queens.append(queen)
    for queen in queens:
        qr, qc = queen
        #check if the pos is in the same column or row
        if row == qr or column == qc:
            return False
        #check diagonals
        if (row + column) == (qr+qc) or (column-row) == (qc-qr):
            return False
    return True

solve(4)

如何修改这段代码，以返回所有解（棋盘配置）的列表，而不是打印它们？

我尝试了以下方式：

def solve(n):
    #prepare a board
    board = [[0 for x in range(n)] for x in range(n)]
    #set initial positions
    solutions = []
    place_queen(board, 0, 0, solutions)
    
def place_queen(board, row, column, solutions):
    """place a queen that satisfies all the conditions"""
    #base case
    if row > len(board)-1:
        solutions.append(board)
        return solutions
    #check every column of the current row if its safe to place a queen
    while column < len(board):
        if is_safe(board, row, column):
            #place a queen
            board[row][column] = 1
            #place the next queen with an updated board
            return place_queen(board, row+1, 0, solutions)
        else:
            column += 1
    #there is no column that satisfies the conditions. Backtrack
    for c in range(len(board)):
        if board[row-1][c] == 1:
            #remove this queen
            board[row-1][c] = 0
            #go back to the previous row and start from the last unchecked column
            return place_queen(board, row-1, c+1, solutions)

然而，只要找到第一个解决方案，它就会返回，因此“solutions”列表只包含一个可能的棋盘配置。

我该如何使其构建整个列表？

- Maximus S

---

在第一个片段中，你把它们打印在哪里？ - aIKid

当当前行超出棋盘大小时，请打印棋盘。 - Maximus S

回答你的“全局”子问题：http://c2.com/cgi/wiki?GlobalVariablesAreBad - jonrsharpe

关于 print 和 return 的区别：https://dev59.com/sWsz5IYBdhLWcg3wxq4V （请不要在一个帖子中问多个问题，特别是当其中一个是重复的）。 - jonrsharpe

谢谢你提供的链接@jonrsharpe，但恐怕那不是我要问的。print和return之间的区别非常明显。让我困扰的是，当我可以逐个轻松打印预期结果时，我很难想出如何返回一组预期结果。 - Maximus S

Answer 1

利用Python的强大功能！我建议使用yield来返回找到的解决方案，而不是使用return。这样，您就可以创建一个所有解决方案的生成器。如果确实需要，将其转换为列表也很容易，只需使用以下表示法：

[ solution for solution in solve(4) ]

或者简单地说

list(solve(4))

编辑：

在您的情况下，solve()和place_queen()必须成为生成器。在solve()中，您应该最后做以下操作：return place_queen(board, 0, 0)。通过这样做，您将会返回一个生成器。(您也可以使用for solution in place_queen(board, 0, 0): yield solution，但那只是传递了产生的值。)

在place_queen()中，代替像return place_queen(board, row+1, 0)这样的返回语句，您应该这样做：for solution in place_queen(board, row+1, 0): yield solution。

编辑2：

#!/usr/bin/env python

def solve(n):
    #prepare a board
    board = [[0 for x in range(n)] for x in range(n)]
    #set initial positions
    return place_queen(board, 0, 0)

def place_queen(board, row, column):
    """place a queen that satisfies all the conditions"""
    #base case
    if row > len(board)-1:
        yield board
    #check every column of the current row if its safe to place a queen
    while column < len(board):
        if is_safe(board, row, column):
            #place a queen
            board[row][column] = 1
            #place the next queen with an updated board
            for solution in place_queen(board, row+1, 0):
                yield solution
            return
        else:
            column += 1
    #there is no column that satisfies the conditions. Backtrack
    for c in range(len(board)):
        if board[row-1][c] == 1:
            #remove this queen
            board[row-1][c] = 0
            #go back to the previous row and start from the last unchecked column
            for solution in place_queen(board, row-1, c+1):
                yield solution

def is_safe(board, row, column):
    """ if no other queens threaten a queen at (row, queen) return True """
    queens = []
    for r in range(len(board)):
        for c in range(len(board)):
            if board[r][c] == 1:
                queen = (r,c)
                queens.append(queen)
    for queen in queens:
        qr, qc = queen
        #check if the pos is in the same column or row
        if row == qr or column == qc:
            return False
        #check diagonals
        if (row + column) == (qr+qc) or (column-row) == (qc-qr):
            return False
    return True

import sys, pprint
sys.setrecursionlimit(10000)
for solution in solve(8):
    pprint.pprint(solution)

- Alfe

---

这是一个有趣的方法。然而，用yield替换所有的return会得到一个place_queen generator object，而我期望得到的是一个list类型的生成器（这样你的解决方案才能起作用）。也许我对生成器还有些不理解。你有什么想法吗？ - Maximus S

当然，如果你使用yield，那么你就是一个生成器，而不仅仅是一个函数。谁要使用你，就应该迭代你，而不仅仅是期望得到一个值。与其使用solution = solve(4)，我们应该像这样做：for solution in solve(4): print solution或类似的操作。 - Alfe

很遗憾，你的代码不能直接运行（在is_safe()函数中缺少变量queens），否则我会很快采用我的方法来修改你的代码。 - Alfe

这种方法似乎不起作用，因为在place_queen()内部的每个循环中没有return语句，导致row不断增加，从而出现索引超出范围的错误。 - Maximus S

顺便说一下，代码已经被编辑过了，所以如果你复制粘贴它，它会正常工作。 - Maximus S

我采用了你的解决方案并粘贴了生成的代码。由于对称性，它在8×8棋盘上找到了92个解决方案。 - Alfe

Answer 2

当找到一个解决方案时，您需要调整代码以进行回溯，而不是返回。只有在回溯到第一行时才希望返回（因为这表示您已经探索了每个可能的解决方案）。

我认为，如果您稍微更改代码结构并无条件地遍历列，则最容易实现回溯逻辑，当您超出行或列范围时，回溯逻辑会触发：

import copy

def place_queen(board, row, column, solutions):
    """place a queen that satisfies all the conditions"""
    while True: # loop unconditionally
        if len(board) in (row, column): # out of bounds, so we'll backtrack
            if row == 0:   # base case, can't backtrack, so return solutions
                return solutions
            elif row == len(board): # found a solution, so add it to our list
                solutions.append(copy.deepcopy(board)) # copy, since we mutate board

            for c in range(len(board)): # do the backtracking
                if board[row-1][c] == 1:
                    #remove this queen
                    board[row-1][c] = 0
                    #go back to the previous row and start from the next column
                    return place_queen(board, row-1, c+1, solutions)

        if is_safe(board, row, column):
            #place a queen
            board[row][column] = 1
            #place the next queen with an updated board
            return place_queen(board, row+1, 0, solutions)

        column += 1

这个方法适用于小型棋盘（例如4），但是如果您尝试用它来解决更大的棋盘问题，您将会遇到Python的递归限制。Python没有优化尾递归，所以当代码从一行转移到另一行时，它会建立许多堆栈帧。

幸运的是，尾递归算法通常很容易转换为迭代算法。以下是如何将上面的代码转换为迭代算法：

import copy

def place_queen_iterative(n):
    board = [[0 for x in range(n)] for x in range(n)]
    solutions = []
    row = column = 0

    while True: # loop unconditionally
        if len(board) in (row, column):
            if row == 0:
                return solutions
            elif row == len(board):
                solutions.append(copy.deepcopy(board))

            for c in range(len(board)):
                if board[row-1][c] == 1:
                    board[row-1][c] = 0

                    row -= 1     # directly change row and column, rather than recursing
                    column = c+1
                    break        # break out of the for loop (not the while)

        elif is_safe(board, row, column):   # need "elif" here
            board[row][column] = 1

            row += 1      # directly update row and column
            column = 0

        else:             # need "else" here
            column += 1   # directly increment column value

请注意，迭代版本不需要使用不同的行和列起始值进行调用，因此这些不需要作为参数。同样，棋盘和结果列表设置可以在开始循环之前完成，而不是在辅助函数中完成（进一步减少函数参数）。

稍微更具Python风格的版本是一个生成器，它会yield其结果，而不是将其收集到列表中并在最后返回，但这只需要进行一些小的更改（只需yield而不是调用solutions.append）。使用生成器也可能让您跳过每次找到解决方案时复制棋盘，只要您能够确信生成器的使用者在推进生成器之前立即使用结果（或创建自己的副本）。

另一个想法是简化您的棋盘表示。您知道在给定行中只能有一个皇后，那么为什么不只在一维列表中存储放置皇后的列（使用哨兵值，如1000表示未放置皇后）？因此，[1, 3, 0, 2]将是4皇后问题的解决方案，在(0, 1)，(1, 3)，(2, 0)和(3, 2)处放置皇后（如果需要，您可以使用enumerate获取这些元组）。这使您避免了回溯步骤中的for循环，并且可能使检查一个方块是否安全更容易，因为您不需要在棋盘上搜索皇后。

针对您的其他问题进行编辑：

在Q1点，您必须深度复制棋盘，否则您将得到指向同一棋盘的引用列表。比较：

board = [0, 0]
results.append(board)    # results[0] is a reference to the same object as board
board[0] = 1             # this mutates results[0][0] too!
result.append(board)     # this appends another reference to board!
board[1] = 2             # this also appears in results[0][1] and result[1][1]

print(board)   # as expected, this prints [1, 2]
print(results) # this however, prints [[1, 2], [1, 2]], not [[0, 0], [1, 0]]

对于第二个问题，你需要使用return来停止代码的执行。如果你想要更清楚地表达返回值不重要，可以将return语句与递归调用分开。

place_queen(board, row+1, 0)
return

请注意，你当前的代码可能可以工作，但它做了一些可疑的事情。你正在使用超出边界（即row == len(board)）的row值调用is_safe函数，只有因为你的is_safe实现将其报告为不安全（而没有崩溃），你才能适当地回溯。当你在回溯代码中处于第0行（即运行的最后），你之所以能正确退出，只是因为for循环在board[-1]（即最后一行）中找不到任何1值。我建议你进一步重构你的代码，以避免依赖这样的怪癖来保证正确的操作。

- Blckknght

---

谢谢你的出色回答。就像你所说，我最好使用一个更简单的板子表示法。我更新了我的代码。你介意看一下并回答新增的问题吗？ - Maximus S

@MaximusS：我已经编辑了答复你的额外问题，并对你最新的代码进行了一些额外的评论。 - Blckknght

另外，我从某个地方听说应该避免使用 deepcopy()。你知道为什么吗？ - Maximus S

@MaximusS：通常情况下，如果不需要复制数据，最好避免这样做，因为它往往会很慢（而且显然会增加程序的内存使用量）。但是，如果您需要复制一个复杂对象，copy.deepcopy可能是最好的方法。对于像（非嵌套）列表这样的简单对象，您可以用其他方式进行复制（例如list(old_lst)或old_lst[:]），但对于像board这样的嵌套结构来说，这些方法是不够的。 - Blckknght

非常感谢您的巨大帮助。我刚刚发布了另一个与此类似的问题。有空的时候请看一下。https://dev59.com/BnrZa4cB1Zd3GeqPzCqC - Maximus S