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)

Ich habe Python-Code für das N-queen-Problem geschrieben und es gibt jede mögliche Lösung aus, wenn sie gefunden wird. Ich möchte diesen Code jedoch so ändern, dass er eine Liste aller Lösungen (Platinenkonfigurationen) zurückgibt, anstatt sie zu drucken. Ich habe versucht, den Code wie folgt zu ändern:

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)

Dies kehrt jedoch zurück, sobald die erste Lösung gefunden wurdesolutions besteht nur aus einer möglichen Platinenkonfiguration. Schon seitprint vs. return Ich würde es sehr begrüßen, wenn mir jemand zeigen könnte, wie man den obigen Code ändert und wie man ähnliche Probleme in Zukunft angeht.

Ich gehe davon aus, dass die Verwendung einer globalen Variablen funktionieren würde, habe aber irgendwo gelernt, dass die Verwendung globaler Variablen für ein solches Problem nicht empfehlenswert ist. Könnte das auch jemand erklären?

BEARBEITEN:

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

Das oben Gesagte gibt alle gefundenen Lösungen zurück, anstatt sie zu drucken. Ich habe noch ein paar Fragen (verwandte Teile sind im obigen Code mit Q1 und Q2 gekennzeichnet)

Warum müssen wirsolutions.append(deepcopy(board))? Mit anderen Worten, was genau passiert, wenn wir es tunsolutions.append(board) und warum führt dies dazu, dass das ursprüngliche Board angehängt wird, das ist[[0,0,0,0] ...]?Warum stoßen wir auf ein Problem, wennreturn place_queen(board, row+1, 0) wird ersetzt durchplace_queen(board, row+1, 0)? Wir geben nichts zurück (oderNone), aber ohnereturn Die Liste geht aus dem Index.