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

Question

So the code is about finding the least amount of rounds a knight in chess would take to move from start to goal. And also the code must be recursive. I have a problem with this code. . My problem is that it's not runing through all stacks but only through one "path" of possible moves and then deliveres the amount of rounds needed in that path.

For example with print(knight([1,1], [5,2], [])) it returns 17 instead of 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

I assume your besucht is storing the path. I don't understand the use of it, as it is not used anywhere in the code. Anyways, I will stop pretending I am on CodeReview and answer your question.

The reason of the bug is because you're passing the list besucht around. When you pass lists as function arguments, it is passed as a reference/pointer instead of a copy of the list. As a result, the later function calls will modify the original besucht, causing bugs in if possibles[i] in besucht.

To fix this, instead pass in a copy of the path. (Obviously it's not the most efficient way, but it works here). See code.

# 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], []))

(Note: Your code using DFS for a shortest path is extremely inefficient. Please search up Breath-First Search so other people on stackoverflow don't flame you for your inefficient code.)