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

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仅包含一个可能的电路板配置。由于打印与退货对于回溯算法一直困扰着我，因此，如果有人可以向我展示如何修改上述代码以及将来如何解决类似问题，我将不胜感激。

我认为使用全局变量是可行的，但是我从某个地方了解到，不建议将全局变量用于此类问题。有人也可以解释吗？

编辑:

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)

为什么我们需要solutions.append(deepcopy(board))？换句话说，当我们执行solutions.append(board)时到底发生了什么，为什么会导致附加初始板[[0,0,0,0] ...]呢？

将return place_queen(board, row+1, 0)替换为place_queen(board, row+1, 0)时，为什么会遇到问题？我们实际上并没有返回任何内容(或None)，但是如果没有return，列表将不在索引之内。

最佳答案

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

我认为，如果您稍微更改代码的结构并无条件地在列上循环，那么当行或列超出范围时，回溯逻辑就会起作用，这是最容易做到的:

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的结果，而不是将它们收集在列表中以在末尾返回，但是只需要进行一些小的更改(只是yield而不是调用solutions.append)。使用生成器还可以让您在每次有解决方案时都跳过复制电路板的过程，只要您可以依靠生成器的使用者立即使用结果(或制作自己的副本)，然后再使生成器前进即可。

另一个想法是简化您的董事会代表。您知道给定行中只能有一个女王/王后，所以为什么不只将一列存储在一维列表中(带有前哨值，如1000指示没有女王/王后被放置)？因此，[1, 3, 0, 2]将是4皇后问题的一种解决方案，将Queent设置为(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

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

关于python - Python : how to return solutions instead of printing them?中的N皇后回溯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20514267/