递归代码的问题 - n 皇后问题

Question

我正在尝试递归解决 n 皇后问题。请看一下这段代码：

def solve(n,chess_arr,forbidden_cells=[]):

  print("1.",n,chess_arr,forbidden_cells)

  if n>(n*n)-len(forbidden_cells):
    return False

  elif n==1:
    printchessboard(chess_arr)
    return True

  else:
    for i in range(len(chess_arr)):
      for j in range(len(chess_arr[i])):

        print("2. ",n,(i,j),(i,j) not in forbidden_cells,forbidden_cells)

        if (i,j) not in forbidden_cells:
          chess_arr[i][j]=["Q"]
          forbidden_row=i
          forbidden_col=j
          partial_forbidden_cells=create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells)
          forbidden_cells.extend(partial_forbidden_cells)

          if solve(n-1,chess_arr,forbidden_cells):
            return True
          else:
            chess_arr[i][j]=[]
            for partial in partial_forbidden_cells:
              forbidden_cells.remove(partial)
    return False


def create_partial_forbidden(n,chess_arr,forbidden_row,forbidden_col,forbidden_cells):
  partial_forbidden_cells=[]

  ######################################### This block takes care of rows and columns #################################################
  partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col )\
                          for i in range(-n,n)\
                          if (forbidden_row+i>=0 and forbidden_row+i<n and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  partial_forbidden_cells.extend([(forbidden_row,forbidden_col+i )\
                          for i in range(-n,n)\
                          if (forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  # i!=0 ensures that the place where the queen is located is not repeated again
  ######################################### This block takes  care of the diagonals ###################################################
  partial_forbidden_cells.extend([(forbidden_row+i,forbidden_col+i)\
                          for i in range(-n,n) \
                          if (forbidden_row+i>=0 and\
                              forbidden_row+i<n and forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])

  partial_forbidden_cells.extend([(forbidden_row-i,forbidden_col+i) \
                          for i in range(-n,n) \
                          if (forbidden_row-i>=0 and\
                              forbidden_row-i<n and forbidden_col+i>=0 and\
                              forbidden_col+i<n and i!=0  and\
                          (forbidden_row+i,forbidden_col) not in forbidden_cells )])
  # i!=0 ensures that the place where the queen is located is not repeated again
  #####################################################################################################################################

  #print("forbidden cells are ", forbidden_cells)
  return partial_forbidden_cells

我在这里面临概念上的疑问。虽然第一个打印语句在某些情况下总是返回非空的forbidden_cells列表，但第二个打印语句总是返回一个空列表。我很茫然为什么会这样？有人可以解释一下吗？

我的期望：由于我将禁止列表作为参数传递，因此我希望它在每次迭代时都会更新，并且在每次迭代时，我希望处理最新的和更新的禁止列表。

典型输出如下：

1. 3 [[['Q'], [], [], []], [[], [], [], []], [[], [], [], []], [[], [], [], []]] [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (0, 3), (1, 1), (2, 2), (3, 3)]
2.  4 (0, 1) True []

感谢您的帮助！

Answer 1

您的代码中存在以下问题：

基本情况不应该是
```
n == 1
```
，而是
```
n == 0
```
，如
```
solve
```
中，
```
n
```
的值代表你还需要在棋盘上放置多少个皇后，当你已放置所有皇后。否则你停下来很快，就不会放置最后一个皇后。但另请参阅下一点，因为它也会影响这一点：
```
n
```
代表棋盘的大小，但在
```
solve
```
中它也代表棋盘上还剩下多少个皇后。这意味着在
```
solve
```
的递归调用中，不再有第一个含义中的
```
n
```
。然而，您可以在不同的地方使用它，就好像它代表了电路板的大小一样。例如在这个公式中：
```
if n>(n*n)-len(forbidden_cells):
```
这里的意思是，如果要放置的皇后数量（
```
n
```
）大于单元格总数（
```
n*n
```
）减去禁止的单元格，我们应该回溯。正如您所看到的，这里存在冲突。
```
n*n
```
不是棋盘的大小，而是一个无意义的值（仍待放置的皇后数量，...平方）。

这种混乱也会对
```
create_partial_forbidden
```
的执行产生严重影响，其中
```
range(-n,n)
```
最终不会覆盖整个列或行。

为了解决这个问题，我建议保留
```
n
```
表示板的大小，而是将
```
solve
```
的第一个参数命名为
```
queens
```
，以便进行区分。在
```
solve
```
顶部添加一条语句，设置变量
```
n
```
来表示板的尺寸（宽度），因为我们实际上不需要参数：
```
n = len(chess_arr)
```
然后您需要在代码的其余部分中体现这种区别：
1. 回溯检查应改为：
```
if queens > n*n-len(forbidden_cells):
```
2. 基本情况检查应更改为：
```
elif queens==0:
```
3. 递归调用应传递
```
queens-1
```
  作为第一个参数
在
```
create_partial_forbidden
```
中，您重复出现错误，因为您多次复制了以下条件：
```
(forbidden_row+i,forbidden_col) not in forbidden_cells )  
```
但这仅在第一次出现时才是正确的。在其他三种情况下，
```
+i
```
应根据上下文进行调整（有时应将其添加到列中，有时应从行中减去......等等）。由于此错误，您将返回比预期更少的禁止单元格。

如果你解决了以上几点，它应该可以工作。补充几点：

我不会将lists分配给棋盘的单元格。该列表包装器没有任何作用。只需分配字符串，例如用
```
="Q"
```
代替
```
=["Q"]
```
，用
```
=""
```
代替
```
=[]
```
。您必须相应地调整您的
```
printchessboard
```
函数，但对我来说这更有意义。
函数
```
create_partial_forbidden
```
不使用
```
chess_arr
```
参数，所以我就放弃它。
不要分配“可变”的默认参数值。所以 forbidden_cells=[] 是不好的做法。这种意想不到的效果已经欺骗了您之前的许多程序员。相反，强制调用者显式提供参数或提供
```
None
```
作为默认值，但随后您需要在函数中添加一条语句，用空列表替换默认值。
printchessboard
函数可以将
```
forbidden_cells
```
作为额外参数，以便您可以标记输出中禁止哪些单元格。这对于调试很有用。

这是解决上述问题的代码，并提供了针对标准棋盘尺寸 (8) 运行的示例：

# Added parameter for more clues in the output def printchessboard(chess_arr, forbidden_cells): for i, row in enumerate(chess_arr): for j, cell in enumerate(row): print("X" if (i, j) in forbidden_cells and cell == "." else cell, end=" ") print() print() # Rename first parameter, remove mutable default value from last paramter def solve(queens, chess_arr, forbidden_cells): n = len(chess_arr) # Make distinction between queens and n. # Corrected backtracking condition: if queens > n*n-len(forbidden_cells): return False # Corrected base case condition elif queens==0: return True else: for i in range(len(chess_arr)): for j in range(len(chess_arr[i])): if (i,j) not in forbidden_cells: chess_arr[i][j] = "Q" # not ["Q"] forbidden_row = i forbidden_col = j # Drop the chess_arr argument: partial_forbidden_cells = create_partial_forbidden(n, forbidden_row, forbidden_col, forbidden_cells) forbidden_cells.extend(partial_forbidden_cells) # Pass queens-1 as argument if solve(queens-1, chess_arr, forbidden_cells): return True else: chess_arr[i][j] = "." # Not list, but string for partial in partial_forbidden_cells: forbidden_cells.remove(partial) return False # chess_arr parameter is not used def create_partial_forbidden(n, forbidden_row, forbidden_col, forbidden_cells): partial_forbidden_cells=[] partial_forbidden_cells.extend([ (forbidden_row + i, forbidden_col) for i in range(-n, n) if forbidden_row + i >= 0 and forbidden_row + i < n and (forbidden_row + i, forbidden_col) not in forbidden_cells ]) partial_forbidden_cells.extend([ (forbidden_row,forbidden_col + i) for i in range(-n, n) if (forbidden_col + i >= 0 and forbidden_col + i < n and i!=0 and # correction of tuple, here and in the next blocks (forbidden_row,forbidden_col+i) not in forbidden_cells) ]) partial_forbidden_cells.extend([ (forbidden_row + i, forbidden_col + i) for i in range(-n, n) if (forbidden_row + i >=0 and forbidden_row + i < n and forbidden_col + i >=0 and forbidden_col + i < n and i!=0 and (forbidden_row + i, forbidden_col + i) not in forbidden_cells) ]) partial_forbidden_cells.extend([ (forbidden_row - i,forbidden_col + i) for i in range(-n, n) if (forbidden_row - i >= 0 and forbidden_row - i < n and forbidden_col + i >= 0 and forbidden_col + i < n and i!=0 and (forbidden_row - i, forbidden_col + i) not in forbidden_cells) ]) return partial_forbidden_cells def main(): n = 8 chess_arr = [ ['.'] * n for _ in range(n) ] solve(n, chess_arr, []) print("solution:") printchessboard(chess_arr, []) main()

还有改进的空间：

forbidden_cells
应该是一个集合而不是一个列表。
solve
时考虑仅将皇后放置在
```
特定
```
行上，您将获得更高的效率。如果这是不可能的，您已经可以原路返回。
实现有效解决 n 皇后问题的 Python 算法
。

递归代码的问题 - n 皇后问题

问题描述投票：0回答：1

1个回答

这是解决上述问题的代码，并提供了针对标准棋盘尺寸 (8) 运行的示例：

最新问题

递归代码的问题 - n 皇后问题

问题描述 投票：0回答：1

1个回答

这是解决上述问题的代码，并提供了针对标准棋盘尺寸 (8) 运行的示例：

最新问题

问题描述投票：0回答：1