Python中的N皇后回溯:如何返回解决方案而不是打印解决方案? [英] N-queen backtracking in Python: how to return solutions instead of printing them?
问题描述
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皇后问题编写了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仅包含一个可能的电路板配置.由于 print vs. return 在回溯算法方面一直让我感到困惑，因此，如果有人可以向我展示如何修改上述代码以及以后如何解决类似问题，我将不胜感激.
我认为使用全局变量是可行的，但是我从某个地方得知，不建议将全局变量用于此类问题.有人也可以解释吗?
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
请注意，您当前的代码可能有效，但是正在做一些可疑的事情.您正在使用超出范围(row == len(board))的row值调用is_safe，这仅仅是因为您的is_safe实现将其报告为不安全(不会崩溃)，因此您进行了适当的回溯.而且，当您在行0的回溯代码中(运行结束时)，您只能正确退出，因为for循环在board[-1]中找不到任何1值(即，最后一行).我建议对代码进行更多重构，以避免依赖此类怪癖来进行正确的操作.
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)
I wrote Python code for N-queen problem and it prints every possible solution whenever it's found. However, I would like to modify this code so that it returns a list of all the solutions(board configurations) instead of printing them. I tried modifying the code like following:
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)
However, this returns as soon as the first solution is found, so solutions only consists of one possible board configuration. Since print vs. return has been confusing to me for backtracking algorithms, I would very much appreciate it if someone could show me how to modify the above code, and how to approach similar problems in future.
I assume using a global variable would work, but I learned from somewhere that using global variables for such problem is discouraged. Could someone explain this too?
EDIT:
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
The above returns all the found solutions instead of printing them. I have a few more questions (related parts are marked Q1 and Q2 in above code)
- Why do we need to
solutions.append(deepcopy(board))? In other words, what exactly is happening when we dosolutions.append(board)and why does this lead to appending the initial board which is[[0,0,0,0] ...]? - Why do we run into a problem when
return place_queen(board, row+1, 0)is replaced byplace_queen(board, row+1, 0)? We are not actually returning anything (orNone), but withoutreturnthe list goes out of index.
You need to adapt your code to backtrack after a solution is found, rather than returning. You only want to return when you find yourself backtracking off the first row (because that indicates that you've explored every possible solution).
I think this is easiest to do if you change the structure of your code a bit and loop unconditionally over the columns, with the backtracking logic kicking in when you're out of bounds on either the row or column:
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
This will work for small boards (like 4), but you'll hit Python's recursion limit if you try it for larger board sizes. Python doesn't optimize out tail recursion, so this code builds up a lot of stack frames as it shifts from one row to another.
Fortunately, tail recursive algorithms are usually easy to turn into iterative algorithms. Here's how that can be done to the code above:
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
Note that the iterative version doesn't need to be called with different row and column starting values, so those aren't needed as parameters. Similarly, the board and result list setup can be done before starting the loop, rather than in a helper function (further reducing the function parameters).
A slightly more Pythonic version of this would be a generator that yields its results, rather than collecting them up in a list to return at the end, but that only requires a few minor changes (just yield instead of calling solutions.append). Using a generator might also let you skip copying the board each time you have a solution, as long as you can depend on the generator's consumer using the result immediately (or making its own copy) before it advances the generator again.
Another idea would be to simplify your board representation. You know that there can only ever be a single queen in a given row, so why not just store the column where it has been placed in a one-dimensional list (with a sentinel value, like 1000 indicating no queen having been placed)? So [1, 3, 0, 2] would be a solution to the 4-queens problem, with queens at (0, 1), (1, 3), (2, 0) and (3, 2) (you could get these tuples with enumerate, if you needed them). This lets you avoid the for loop in the backtracking step, and probably makes checking if a square is safe easier too, since you don't need to search the board for the queens.
Edit to address your additional questions:
At point Q1, you must deep copy the board because otherwise you'll end up with a list of references to the same board. Compare:
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]]
As for Q2, you need to return to stop the code from running further. You could separate the return statement from the recursive call, if you want to make it more clear that the return value is not significant:
place_queen(board, row+1, 0)
return
Note that your current code may work, but it's doing some dubious stuff. You're calling is_safe with row values that are out of bounds (row == len(board)), and it's only because your is_safe implementation reports them as unsafe (without crashing) that you backtrack appropriately. And when you're in the backtracking code at row 0 (at the very end of the run), you only quit correctly because the for loop can't find any 1 values in board[-1] (that is, the last row). I suggest refactoring your code a bit more to avoid relying on such quirks for correct operation.
这篇关于Python中的N皇后回溯:如何返回解决方案而不是打印解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
