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)

Я написал код Python для задачи N-queen, и он печатает все возможные решения, когда бы они ни были найдены. Однако я хотел бы изменить этот код так, чтобы он выводил список всех решений (конфигураций платы) вместо их печати. Я попытался изменить код следующим образом:

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 список выходит из индекса.