时间戳

首页 > 解决方案 > Python“骑士之旅”回溯代码不起作用

python - Python“骑士之旅”回溯代码不起作用

问题描述

在观看了有关回溯的 Computerphile 视频后，我决定尝试针对不同的问题实现此算法。当我的代码开始无休止地迭代深度 46-53 时，我的代码似乎一直工作到深度 ~48。这不是内存问题，对于 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 次左右的尝试，但被卡在了这些表上并一遍又一遍地迭代。

标签： pythonnumpyrecursionknights-tour

解决方案

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

在您的代码中，我看不到在哪里depth增加，尽管它nummove应该从 1 开始，而不是 0 是多余的，因为您已经进行了移动 0。我修改了您的代码以返回结果，而不是printand exit, removed 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]

推荐阅读