Python "The Knight's Tour" 回溯代码无效

Question

观看了有关回溯的 Computerphile 视频后，我决定尝试针对不同的问题实施此算法。当它开始无休止地迭代深度 46-53 时，我的代码似乎一直工作到深度 ~48。这不是内存问题，至于 6x6 table 它在深度 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)

代码基本上应该检查它是否可以与骑士一起去某个新位置，直到它不能再前进为止，此时递归调用后的代码部分将其再次重置。在看到示例 tables 后，它似乎正确地创建了前 50 次左右的尝试，但卡在这些尝试中并一遍又一遍地迭代。

Answer 1

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

在你的代码中，我看不到 depth 在哪里递增，尽管它与 nummove 是多余的，它应该从 1 开始，而不是 0，因为你已经移动了 0。我重新做了您的代码 return 结果，而不是 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]

Python "The Knight's Tour" 回溯代码无效

Python "The Knight's Tour" backtracking code not working

python

recursion

numpy

knights-tour