为什么我的 Python 中的递归骑士代码仅在运行第一堆栈中？

Question

所以代码是关于寻找国际象棋中的骑士从起点到终点所需的最少回合数。而且代码必须是递归的。我对这段代码有疑问。 .我的问题是它并没有遍历所有堆栈，而是仅遍历可能移动的一个“路径”，然后传递该路径中所需的回合数。

例如 print(knight([1,1], [5,2], [])) 它 returns 17 而不是 3

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

def knight(start, goal, visited):
    if start == goal:
        return 0      
    else:
        visited.append(start)
        possibles =[]
        makeable= []
        for x in range(8):
            possibles.append([start[0] + moves[x][0],start[1] + moves[x][1]])
        for i in range(8):
            if possibles[i]  not in visited and possibles[i][0]<9 and possibles[i][1]<9 and possibles[i][0]>0 and possibles[i][1]>0:
                makeable.append(knight(possibles[i],goal,visited))

        if makeable:
            return min(makeable)+1
        else:
            return 99   
            
                
                  
    
print(knight([1,1], [5,2], []))

Answer 1

我假设您的 besucht 正在存储路径。我不明白它的用法，因为它没有在代码中的任何地方使用。无论如何，我将停止假装我在 CodeReview 上并回答你的问题。

错误的原因是因为您正在传递列表 besucht。当您将列表作为函数参数传递时，它将作为列表的 reference/pointer 而不是 copy 传递。结果，后面的函数调用将修改原来的besucht，导致if possibles[i] in besucht.

中的错误

要解决此问题，请传入路径的副本。（显然这不是最有效的方式，但它在这里有效）。见代码。

# python
moves = ([1,2],[2,1],[-1,2],[-1,-2],[1,-2],[2,-1],[-2,1],[-2,-1])

def springerzug(start, end, path, sofar = 0):
    if start == end:
        return 0
    # Terminate if path is too long
    if len(path) > 9:
        return 999
    # omit the else
    possibles = []
    ergebnisse = [98] # default value

    for x in range(8):
        possibles.append([start[0] + moves[x][0], start[1] + moves[x][1]])

    for i in range(8):
        if 0 < possibles[i][0] < 9 and 0 < possibles[i][1] < 9 \
            and possibles[i] not in path:
                ergebnisse.append(springerzug(possibles[i], end, path.copy() + [possibles[i]]))

    return min(ergebnisse)+1
            
                
                  
    
print(springerzug([1,1], [5,2], []))

（注意：您的代码使用 DFS 作为最短路径效率极低。请搜索 Breath-First Search，这样 Whosebug 上的其他人就不会因为您的低效代码而责备您。）

为什么我的 Python 中的递归骑士代码仅在运行第一堆栈中？

Why does my recursive knight code in Python only run the first stack?

python

recursion

chess

为什么我的 Python 中的递归骑士代码仅在 运行 第一堆栈中？

Why does my recursive knight code in Python only run the first stack?

python

recursion

chess

为什么我的 Python 中的递归骑士代码仅在运行第一堆栈中？