Python "The Knight's Tour"回溯代码不起作用

Question

在回溯上观看了Computerphile视频后，我决定尝试为不同的问题实现此算法。我的代码似乎一直工作到深度 ~48 时，它开始无休止地迭代深度 46-53。这不是内存问题，对于 6x6 表，它在深度 20 附近同样卡住。

table = np.zeros((8, 8)) - 1
table[0, 0] = 0
knightDOWN = [1, 2, 2, 1, -1, -2, -2, -1]
knightRIGHT = [2, 1, -1, -2, -2, -1, 1, 2]
depth = 0
def correctmove(move, startROW, startCOL):
newROW = startROW + knightDOWN[move]
newCOL = startCOL + knightRIGHT[move]
if newROW < 0 or newROW > 7:
return False
if newCOL < 0 or newCOL > 7:
return False
if table[newROW, newCOL] != -1:
return False
return True
def goBoard(startROW, startCOL, nummove):
if depth == 64:
print(table)
exit()
for x in range(0, 8):
if correctmove(x, startROW, startCOL):
print(table[startROW, startCOL])
startROW += knightDOWN[x]
startCOL += knightRIGHT[x]
table[startROW, startCOL] = nummove
nummove += 1
goBoard(startROW, startCOL, nummove)
table[startROW, startCOL] = -1
startROW -= knightDOWN[x]
startCOL -= knightRIGHT[x]
nummove -= 1
return
goBoard(0, 0, 0)

代码基本上应该检查它是否可以与骑士一起移动到某个新位置，直到它无法再向前移动，此时递归调用后的代码部分会再次重置它。看到示例表后，它似乎正确地创建了前 50 次左右的尝试，但卡在这些尝试上并一遍又一遍地迭代。

Answer 1

这应该需要很长时间，并且回溯很多，因为您使用的是需要穷尽很多可能性的蛮力算法。

在您的代码中，我没有看到depth在哪里递增，尽管它与应该从 1 开始而不是 0 的nummove是多余的，因为您已经移动了 0。 我重新设计了你的代码以返回结果，而不是print和exit，删除了numpy，而是用直接的Python重写它，并简化了它 - 撤消了更少的步骤：

KNIGHT_MOVES = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
table = [[-1] * 8 for _ in range(8)]
table[0][0] = 0
def correctmove(row, col):
return 0 <= row <= 7 and 0 <= col <= 7 and table[row][col] == -1
def goBoard(startROW, startCOL, nummove):
if nummove == 64:
return table
for down, right in KNIGHT_MOVES:
row = startROW + down
col = startCOL + right
if correctmove(row, col):
print(nummove)
table[row][col] = nummove
result = goBoard(row, col, nummove + 1)
if result:
return result
table[row][col] = -1
return None
print(*goBoard(0, 0, 1), sep='n')

大约 2 1/3 分钟后，它会产生以下内容(略微手动重新格式化)：

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