N-Queen-Backtracking in Python: Wie kann man Lösungen zurückgeben, 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 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.