N-Königin backtracking in Python: wie die Rückkehr Lösungen, anstatt Sie zu drucken?

Müssen Sie passen Sie Ihren code, um wieder ansetzen, nachdem eine Lösung gefunden ist, wird anstelle der Rückgabe. Möchten Sie nur zurück, wenn Sie finden, sich selbst backtracking aus der ersten Zeile (weil das zeigt, dass Sie erkundet haben jede mögliche Lösung).

Ich denke, das ist am einfachsten zu tun, wenn Sie ändern die Struktur des Codes ein bit-und-Schleife bedingungslos über die Spalten, mit der backtracking-Logik treten, wenn Sie out of bounds, entweder in der Zeile oder Spalte:

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

Dieser Arbeit wird für kleine boards (wie 4), aber Sie werden hit-Python-Rekursion begrenzen, wenn Sie versuchen, es für größere board-Größen. Python nicht optimieren-out-tail-Rekursion, so ist dieser code baut eine Menge der stack-frames, wie es übergänge von einer Zeile zur anderen.

Glücklicherweise tail-rekursive algorithmen sind in der Regel leicht zu biegen Sie in die iterative algorithmen. Hier ist, wie das getan werden kann, um den obigen code:

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

Beachten Sie, dass die iterative version braucht nicht genannt zu werden, mit verschiedenen Zeile und Spalte ab der Werte, so dass diese nicht benötigt als Parameter. Ebenso werden der Vorstand und der Ergebnis-Liste-setup kann durchgeführt werden, bevor die Schleife, anstatt in eine helper-Funktion (weitere Reduzierung der Parameter der Funktion).

Etwas mehr Pythonic version dieses wäre ein generator, der yields seine Ergebnisse, statt Sie zu sammeln bis in eine Liste, um die Rückkehr am Ende, aber das erfordert nur ein paar kleine änderungen (nur yield statt solutions.append). Mit einem generator können auch lassen Sie überspringen das kopieren der Vorstand jedes mal, wenn Sie eine Lösung haben, solange Sie können, hängen von der generator die Verbraucher mit dem Ergebnis sofort (oder seine Kopie), bevor es Fortschritte, den generator wieder.

Andere Idee wäre, vereinfachen Sie Ihre Geschäftsführung. Sie wissen, dass es immer nur eine einzige Königin, die in einer bestimmten Zeile, also warum nicht speichern nur die Spalte, wo es platziert wurde, in eine eindimensionale Liste (mit sentinel-Wert, wie 1000 angibt, keine Königin verbracht wurde)? So [1, 3, 0, 2] wäre eine Lösung des 4-Damen-problem, mit den Königinnen bei (0, 1), (1, 3), (2, 0) und (3, 2) (man könnte diese Tupel mit enumerate, wenn man Sie brauchte). Dies können Sie vermeiden, die for Schleife in der backtracking Schritt, und wahrscheinlich macht die überprüfung, ob ein Platz ist sicher noch einfacher, da brauchen Sie nicht zu suchen, dem Vorstand für die queens.

Bearbeiten, um auf Ihre weiteren Fragen:

Am Punkt Q1, müssen Sie Tiefe Kopie der platine, weil sonst wirst du am Ende mit einer Liste von Referenzen auf das gleiche board. Vergleichen:

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

Als für Q2, müssen Sie return stoppen Sie den code aus laufen weiter. Könnten Sie trennen die return Anweisung aus dem rekursiven Aufruf, wenn Sie wollen, um es mehr deutlich, dass der return-Wert ist nicht signifikant:

place_queen(board, row+1, 0)
return

Beachten Sie, dass Sie Ihre aktuelle code kann funktionieren, aber Sie tut einige Dubiose Sachen. Sie fordern is_safe mit row Werte, die außerhalb der Grenzen liegen (row == len(board)), und es ist nur, weil Ihr is_safe Umsetzung berichtet Sie als unsicher (ohne Absturz), dass Sie backtrack angemessen. Und wenn Sie in der backtracking-code bei Zeile 0 (ganz am Ende der Ausführung), die Sie nur beenden, richtig, weil der for Schleife finde keine 1 Werte in board[-1] (also der letzten Zeile). Ich schlage vor, refactoring Ihres Codes ein bisschen mehr zu vermeiden, sich auf solche Macken für den korrekten Betrieb.