Python中的回溯——骑士之旅问题

Question

问题陈述：给定一个 N*N 棋盘，其中骑士放置在空棋盘的第一个块上。根据国际象棋骑士的规则，移动必须恰好访问每个方格一次。打印棋盘上访问它们的每个单元格的顺序。如果可能有不止一种解决方案，请打印所有解决方案。

Input :
N = 8
Output:
0  59  38  33  30  17   8  63
37  34  31  60   9  62  29  16
58   1  36  39  32  27  18   7
35  48  41  26  61  10  15  28
42  57   2  49  40  23   6  19
47  50  45  54  25  20  11  14
56  43  52   3  22  13  24   5
51  46  55  44  53   4  21  12

我尝试了使用回溯的递归解决方案，但不太明白这段代码可能存在什么问题。有人可以帮忙吗？非常感谢！

对于

n=2,3,4

它会产生一个预期的空列表。 对于

n=5

，它会产生以下意外输出：

[[[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']], [[0, '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.']]] ..continues

对于

n=8

，程序一直运行，似乎很长时间没有产生输出

def knight(n):
  xy_movements = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(-1,2),(1,-2),(-1,-2)]
  board = [["."]*n for _ in range(n)]
  board[0][0]=0
  current_x=0
  current_y=0
  result=[]

  def backtrack(num):    
    nonlocal n,current_x,current_y
    if num==(n*n)-1:
      result.append(board)
      return
    else:
      for move in xy_movements:
        if current_x+move[0]<0 or current_x+move[0]>=n or\
           current_y+move[1]<0 or current_y+move[1]>=n or\
           board[current_x+move[0]][current_y+move[1]] !=".":
          continue
        else:
          current_x+=move[0]
          current_y+=move[1]
          board[current_x][current_y] = num+1
          backtrack(num+1)
        
        board[current_x][current_y] = "."
        current_x -= move[0]
        current_y -= move[1]

  backtrack(0)
  return result

Answer 1

问题在于

result.append(board)

将附加您拥有的唯一棋盘，而您的回溯算法将继续更新该棋盘，并且在算法的最后将收回它所做的所有移动。所以

board

是空的，除了第一个被放置且从未被删除的 0 之外。这意味着在

result

中，即使找到了解决方案，您现在引用的板几乎是空的。

解决方案很简单：获取该板的副本，并将 that 板附加到

result

列表中：

            result.append([row[:] for row in board])