Почему мой рекурсивный рыцарский код в Python запускает только первый стек?

#python #recursion #chess

#python #рекурсия #шахматы

Вопрос:

Итак, код заключается в нахождении наименьшего количества раундов, которые потребовались бы коню в шахматах, чтобы перейти от начала к цели. А также код должен быть рекурсивным. У меня проблема с этим кодом. . Моя проблема в том, что он проходит не через все стеки, а только через один «путь» возможных ходов, а затем доставляет количество раундов, необходимое на этом пути.

Например, с помощью print(knight([1,1], [5,2], [])) он возвращает 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], []))

1. Я думаю, что больше людей хотели бы вам помочь, если бы вы немного подробнее объяснили, что должен делать этот код и как он должен работать в вашем понимании. Кроме того, всем легче понять код, если он написан на английском языке.

2. спасибо, я сделал. Надеюсь, это поможет понять это

Ответ №1:

Я предполагаю, что вы besucht сохраняете путь. Я не понимаю его использования, поскольку он нигде не используется в коде. В любом случае, я перестану притворяться, что я на CodeReview, и отвечу на ваш вопрос.

Причина ошибки в том, что вы передаете список besucht по кругу. Когда вы передаете списки в качестве аргументов функции, они передаются как ссылка / указатель вместо копии списка. В результате последующие вызовы функций будут изменять исходный 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 для кратчайшего пути, крайне неэффективен. Пожалуйста, выполните поиск сначала с дыханием, чтобы другие люди в stackoverflow не обвиняли вас в неэффективном коде.)