N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?

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 N-Queen-Problem geschrieben und es druckt jede mögliche Lösung, wenn es gefunden wird. Allerdings möchte ich diesen Code so ändern, dass er eine Liste aller Lösungen (Board-Konfigurationen) anstatt sie druckt. 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) 

Allerdings kehrt dies zurück, sobald die erste Lösung gefunden wird, so dass solutions nur aus einer möglichen Platinenkonfiguration bestehen. Da print vs. return mich für die Backtracking-Algorithmen verwirrte, würde ich es sehr schätzen, wenn mir jemand zeigen könnte, wie man den obigen Code modifiziert und wie man in künftigen ähnlichen Problemen anspricht.

Ich nehme an, eine globale Variable zu verwenden, aber ich habe von irgendwo gelernt, dass die Verwendung von globalen Variablen für solches Problem entmutigt wird. Kann man das auch 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 obige gibt alle gefundenen Lösungen zurück, anstatt sie zu drucken. Ich habe noch ein paar Fragen (verwandte Teile sind mit Q1 und Q2 in über Code markiert)

  1. Warum brauchen wir solutions.append(deepcopy(board)) ? Mit anderen Worten, was genau passiert, wenn wir solutions.append(board) [[0,0,0,0] ...] solutions.append(board) und warum führt dies dazu, dass das erste Board, das [[0,0,0,0] ...] ist, [[0,0,0,0] ...] ?
  2. Warum laufen wir in ein Problem, wenn return place_queen(board, row+1, 0) durch place_queen(board, row+1, 0) ersetzt wird place_queen(board, row+1, 0) ? Wir sind eigentlich nicht alles (oder None ) zurück, aber ohne return geht die Liste aus dem Index.

2 Solutions collect form web for “N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?”

Sie müssen Ihren Code an den Backtrack anpassen, nachdem eine Lösung gefunden wurde, anstatt zurückzukehren. Du willst nur zurückkehren, wenn du dich in der ersten Reihe zurückschleppst (weil das anzeigt, dass du jede mögliche Lösung erforscht hast).

Ich denke, das ist am einfachsten zu tun, wenn Sie die Struktur Ihres Codes ein wenig und Schleife bedingungslos über die Spalten ändern, mit der Backtracking-Logik treten, wenn Sie außerhalb der Grenzen auf der Zeile oder Spalte sind:

 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 

Dies wird für kleine Boards (wie 4) funktionieren, aber Sie werden Pythons Rekursionslimit treffen, wenn Sie es für größere Boardgrößen ausprobieren. Python optimiert nicht die Schwanzrekursion, so dass dieser Code eine Menge Stapelrahmen aufbaut, während er von einer Zeile zur anderen verschiebt.

Glücklicherweise sind Schwanz rekursive Algorithmen in der Regel leicht in iterative Algorithmen umzuwandeln. Hier ist, wie das getan werden kann, um den Code oben:

 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 nicht mit unterschiedlichen Zeilen- und Spaltenstartwerten aufgerufen werden muss, also werden diese nicht als Parameter benötigt. Ebenso kann das Board- und Ergebnislisten-Setup vor dem Starten der Schleife durchgeführt werden, anstatt in einer Helper-Funktion (weitere Verringerung der Funktionsparameter).

Eine etwas mehr pythonische Version davon wäre ein Generator, der seine Ergebnisse yield , anstatt sie in einer Liste zu sammeln, um am Ende zurückzukehren, aber das braucht nur ein paar kleinere Änderungen (nur yield statt Aufruf von solutions.append ). Mit einem Generator können Sie auch überspringen Kopieren der Platine jedes Mal, wenn Sie eine Lösung haben, solange Sie sich auf den Generator Verbraucher mit dem Ergebnis sofort (oder machen eine eigene Kopie), bevor es den Generator wieder Fortschritte abhängen können.

Eine andere Idee wäre, Ihre Board-Repräsentation zu vereinfachen. Sie wissen, dass es nur eine einzige Königin in einer gegebenen Reihe geben kann, also warum nicht nur die Spalte speichern, wo sie in eine eindimensionale Liste (mit einem Sentinel-Wert, wie 1000 dass keine Königin platziert wurde) platziert wurde? Also [1, 3, 0, 2] wäre eine Lösung für das 4-Queens-Problem, mit Königinnen bei (0, 1) , (1, 3) , (2, 0) und (3, 2) (du könntest Bekomme diese Tupel mit enumerate , wenn du sie brauchst). Dies lässt Sie vermeiden, die for Schleife in den Backtracking-Schritt, und wahrscheinlich überprüft, ob ein Platz ist auch einfacher, da Sie nicht brauchen, um das Board für die Königinnen zu suchen.

Bearbeiten, um Ihre zusätzlichen Fragen zu beantworten:

Am Punkt Q1 musst du das Brett tief kopieren, sonst wirst du mit einer Liste von Referenzen auf demselben Brett aufhören. 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]] 

Wie für Q2, müssen Sie return , um den Code zu stoppen weiter zu stoppen. Sie können die return Anweisung vom rekursiven Aufruf trennen, wenn Sie es klarer machen wollen, dass der Rückgabewert nicht signifikant ist:

 place_queen(board, row+1, 0) return 

Beachten Sie, dass Ihr aktueller Code funktionieren kann, aber es macht etwas zweifelhaftes Zeug. Sie rufen is_safe mit is_safe an, die außerhalb der Grenzen liegen ( row == len(board) ), und nur deshalb, weil Ihre is_safe Implementierung sie als unsicher (ohne Absturz) meldet, die Sie entsprechend is_safe . Und wenn du in der Backtracking-Code in Zeile 0 (am Ende des Laufes) bist, gehst du nur richtig, weil die for Schleife keine 1 Werte in board[-1] (das heißt, die letzte Zeile ). Ich schlage vor, Ihren Code ein bisschen mehr zu refactoring, um zu vermeiden, auf solche Macken für korrekten Betrieb zu verlassen.

Benutze die Kraft von Python! Ich schlage vor, Ihnen die gefundenen Lösungen zu geben, anstatt sie zurückzugeben. Auf diese Weise haben Sie einen Generator für alle Lösungen erstellt. Um eine Liste daraus zu machen, ist das ziemlich genau dann (falls du es wirklich brauchst) durch die Notation

 [ solution for solution in solve(4) ] 

oder einfach

 list(solve(4)) 

BEARBEITEN:

In deinem Fall solve() und place_queen() muss Generatoren gemacht werden. In solve() solltest du als letztes tun: return place_queen(board, 0, 0) . Hiermit kommst du einen Generator zurück. (Sie könnten auch for solution in place_queen(board, 0, 0): yield solution aber das würde nur die angegebenen Werte for solution in place_queen(board, 0, 0): yield solution .)

In place_queen() anstatt der Rückkehr wie return place_queen(board, row+1, 0) solltest du Sachen wie for solution in place_queen(board, row+1, 0): yield solution .

EDIT2:

 #!/usr/bin/env python def solve(n): #prepare a board board = [[0 for x in range(n)] for x in range(n)] #set initial positions return 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: yield 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 for solution in place_queen(board, row+1, 0): yield solution return 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 for solution in place_queen(board, row-1, c+1): yield solution 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 import sys, pprint sys.setrecursionlimit(10000) for solution in solve(8): pprint.pprint(solution) 
  • Wie man sogar und ungerade Zahlen eines Arrays mit Rekursion summiert
  • Trennungsliste mit Rekursion
  • Lock-Kombinationen für dynamische Sperrgröße
  • Python max Rekursion, Frage über sys.setrecursionlimit ()
  • Rekursionsfunktion funktioniert nicht richtig
  • Python-Rekursions- und return-Anweisungen
  • Integer auf Basis-x-System mit Rekursion in Python
  • Rekursiv finden Sie alle Münzkombinationen, die eine bestimmte Menge produzieren
  • Rekursiver Generator zum Abflachen von verschachtelten Listen
  • Rekursive Funktion, die keine zurückgibt?
  • Python-Funktion kehrt nach Rekursion nicht zurück
  • Python ist die beste Programmiersprache der Welt.