python - Python 中的 N 皇后回溯 : how to return solutions instead of printing them?

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 皇后问题编写了 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 与 return 一直让我对回溯算法感到困惑，如果有人能告诉我如何修改上述代码，以及将来如何处理类似问题，我将不胜感激。 p>

我假设使用全局变量会起作用，但我从某个地方了解到不鼓励使用全局变量来解决此类问题。有人也可以解释一下吗？

编辑:

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

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

它的一个稍微更 Pythonic 的版本是一个生成器，它产生它的结果，而不是将它们收集在一个列表中以在最后返回，但这只需要一些小的改变(只是 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]]

至于Q2，你需要return来阻止代码继续运行。如果您想更清楚地表明返回值不重要，您可以将 return 语句与递归调用分开:

place_queen(board, row+1, 0)
return

请注意，您当前的代码可能有效，但它正在做一些可疑的事情。您正在使用超出范围的 row 值调用 is_safe (row == len(board))，这只是因为您的 is_safe 实现将它们报告为不安全(没有崩溃)，您可以适本地回溯。当你在第 0 行的回溯代码中(在运行的最后)，你只能正确退出，因为 for 循环找不到任何 1 board[-1] 中的值(即最后一行)。我建议再重构一下您的代码，以避免依赖此类怪癖来进行正确操作。