Возврат N-Queen в Python: как вернуть решения вместо их печати?
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
список выходит из индекса.