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