Max*_*s S 6 python recursion backtracking
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)
我为N-queen问题编写了Python代码,并且只要找到它就会打印出所有可能的解决方案.但是,我想修改此代码,以便它返回所有解决方案(板配置)的列表,而不是打印它们.我尝试修改代码如下:
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列表超出索引.您需要调整代码以在找到解决方案后回溯，而不是返回。仅当您发现自己从第一行回溯时才想返回（因为这表明您已经探索了所有可能的解决方案）。
我认为，如果您稍微更改代码的结构并无条件地在列上循环，并且当您超出行或列的范围时回溯逻辑就会启动，这是最容易做到的：
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
这适用于小板（例如 4 个），但如果您尝试较大的板尺寸，则会达到 Python 的递归限制。Python 不会优化尾递归，因此这段代码在从一行移动到另一行时会构建大量堆栈帧。
幸运的是，尾递归算法通常很容易转化为迭代算法。以下是对上面代码的实现方法：
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
请注意，不需要使用不同的行和列起始值来调用迭代版本，因此不需要将它们作为参数。同样，板和结果列表设置可以在开始循环之前完成，而不是在辅助函数中完成（进一步减少函数参数）。
一个稍微更 Pythonic 的版本是一个生成器，它yield存储其结果，而不是将它们收集在列表中以在最后返回，但这只需要一些小的更改（只是而yield不是调用solutions.append）。使用生成器还可以让您在每次获得解决方案时跳过复制电路板，只要您可以依赖生成器的使用者在再次推进生成器之前立即使用结果（或制作自己的副本）。
另一个想法是简化董事会代表。您知道给定行中只能有一个皇后，那么为什么不将其所在的列存储在一维列表中（使用哨兵值，就像1000指示没有放置皇后一样）？因此，这[1, 3, 0, 2]将是 4 皇后问题的解决方案，其中皇后位于(0, 1)、(1, 3)、(2, 0)和（如果需要，(3, 2)可以使用 获得这些元组）。enumerate这可以让您避免for回溯步骤中的循环，并且可能也使检查方格是否安全变得更容易，因为您不需要在棋盘上搜索皇后。
编辑以解决您的其他问题：
在 Q1 点，您必须深度复制该板，否则您最终会得到对同一板的引用列表。比较：
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]]
对于Q2，您需要return停止代码进一步运行。return如果您想更清楚地表明返回值并不重要，您可以将该语句与递归调用分开：
place_queen(board, row+1, 0)
return
请注意，您当前的代码可能可以工作，但它正在做一些可疑的事情。您正在使用超出范围 ( ) 的值is_safe进行调用，这只是因为您的实现将它们报告为不安全（不会崩溃），您才适当地回溯。当您处于第 0 行（在运行的最后）的回溯代码中时，您只能正确退出，因为循环在（即最后一行）中找不到任何值。我建议更多地重构您的代码，以避免依赖此类怪癖来实现正确操作。rowrow == len(board)is_safefor1board[-1]