Python中的N-queen回溯：如何返回解决方案而不是打印它们？

Question

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)

我为N-queen问题编写了Python代码，只要找到它，它就会打印出所有可能的解决方案。但是，我想修改这段代码，以便它返回所有解决方案（板配置）的列表，而不是打印它们。我试着修改代码如下：

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只包含一个可能的板配置。由于print vs.return一直让我对回溯算法感到困惑，如果有人能告诉我如何修改上面的代码，以及将来如何处理类似的问题，我将非常感激。

我认为使用全局变量是可行的，但我从某个地方了解到，不鼓励使用全局变量解决此类问题。有人能解释一下吗？

编辑：

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

def place_queen(board, row, column, solutions):
    """place a queen that satisfies all the conditions"""
    #base case
    if row > len(board)-1:
        #print board
        solutions.append(deepcopy(board)) #Q1
    #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) #Q2
        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) #Q3

上面返回所有找到的解决方案，而不是打印它们。我还有几个问题（相关部分在上面的代码中标记为Q1和Q2）

1. 为什么我们需要solutions.append(deepcopy(board))？换句话说，当我们做solutions.append(board)的时候到底发生了什么，为什么这会导致附加初始的[[0,0,0,0] ...]板？
2. 当return place_queen(board, row+1, 0)被place_queen(board, row+1, 0)替换时，我们为什么会遇到问题？我们实际上并没有返回任何内容（或者None），但是如果没有return，列表就会超出索引范围。

Answer 1

您需要在找到解决方案后调整代码以回溯，而不是返回。你只想在你发现自己从第一行返回时返回（因为这表明你已经探索了所有可能的解决方案）。

我认为，如果稍微更改代码的结构并无条件地在列上循环，并且在超出行或列的界限时启动回溯逻辑，则这是最容易做到的：

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

请注意，迭代版本不需要用不同的行和列起始值调用，因此不需要这些值作为参数。类似地，可以在开始循环之前完成board和result list设置，而不是在helper函数中（进一步减少函数参数）。

稍微更像python的版本是一个生成器，它可以yield生成结果，而不是将结果收集到一个列表中并在最后返回，但这只需要一些小的更改（只是yield，而不是调用solutions.append）。使用生成器还可以让您在每次有解决方案时跳过复制电路板，只要您可以依赖生成器的使用者在再次推进生成器之前立即使用结果（或制作自己的副本）。

另一个想法是简化董事会的代表性。你知道在一个给定的行中只能有一个皇后，那么为什么不把它放在一维列表中的列存储起来（用一个哨兵值，比如1000表示没有放置皇后）？因此[1, 3, 0, 2]将是4-皇后问题的解决方案，皇后位于(0, 1)、(1, 3)、(2, 0)和(3, 2)（如果需要，可以使用enumerate获得这些元组）。这样可以避免回溯步骤中的for循环，并且可能也更容易检查正方形是否安全，因为您不需要在棋盘上搜索皇后。

编辑以解决其他问题：

在第1点，您必须深入复制电路板，否则您将得到对同一电路板的引用列表。比较：

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]]

至于Q2，您需要return来阻止代码进一步运行。如果要更清楚地说明返回值不重要，可以将return语句与递归调用分开：

place_queen(board, row+1, 0)
return

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

Answer 2

使用Python的力量！我建议用你找到的解决方案，而不是用它们。这样，您就为所有解决方案创建了一个生成器。如果你真的需要的话，用这个符号列一个表是非常直接的

[ 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)