Python 递归骑士之旅

Question

我正在尝试用 python 中的递归回溯法解决骑士巡回算法。

解决方案应该是一个包含 24 个记录步骤的矩阵，但它最多只计算 5 个步骤。不进入递归if语句

JUMP_POS = [ (2,1),
             (2,-1),
             (1,2),
             (1,-2),
             (-1,2),
             (-1,-2),
             (-2,1),
             (-2,-1)
           ]

def springen(x, y, nr, matrix):
    matrix_len = len(matrix)
    matrix[x][y] = nr
    if nr == ( (matrix_len*matrix_len) -1 ):
        print("good", matrix)
        return True
    else:
        for pos in JUMP_POS:
            xNeu = x + pos[0]
            yNeu = x + pos[1]

            if xNeu >= 0 and xNeu < matrix_len and yNeu >= 0 and yNeu < matrix_len:
                if matrix[xNeu][yNeu] == 0: #check, if position is empty
                    if springen(xNeu, yNeu, nr+1, matrix):
                        #this section is not passing
                        return True

        matrix[x][y] = 0
        return False

matrix = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
print(springen(0,0,0,matrix))

Answer 1

我看到的问题是您设置了 yNeu = x + pos[1]，而您的意思可能是 yNeu = y + pos[1]。

另一个潜在的问题是，由于您在第一步和标记未访问的方块时都使用 0，您可以稍后重新访问起始方块，因此请考虑使用 -1 或 None 标记未访问的位置。

Python 递归骑士之旅

Python Recursive Knight Tour

python

recursion

backtracking

knights-tour