Ошибка рекурсивного поиска пути

Question

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

Однако при отладке это кажется, что по мере того как я передаю adjMatrix дальше в рекурсию, он также редактирует верхние уровни и заставляет его не искать дальше, когда он восходит к дереву. Я думаю, что есть что-то, когда я установил newMatrix = adjMatrix, но я не совсем уверен.

def checkio(teleports_string): 
    #return any route from 1 to 1 over all points 
    firstnode, secondnode, size = 0, 0, 8 

    #Makes the adjacency matrix 
    adjMatrix = [[0 for i in range(size)] for j in range(size)] 

    for x in teleports_string: 
     #Assigns Variables 
     if firstnode == 0 and x != ",": 
      #print("Node1:" + x) 
      firstnode = x 
     elif secondnode == 0 and x != ",": 
      #print("Node2:" + x) 
      secondnode = x 
     #Marks connections 
     if firstnode != 0 and secondnode != 0: 
      adjMatrix[int(firstnode) - 1][int(secondnode) - 1] = 1 
      adjMatrix[int(secondnode) - 1][int(firstnode) - 1] = 1 
      firstnode, secondnode = 0, 0 
    print(adjMatrix) 

    return findPath(adjMatrix, 1, "1") 


def findPath(adjMatrix, currentnode, currentpath): 
    if isFinished(currentpath): 
     return currentpath 

    for x in range(0, 8): 
     if adjMatrix[currentnode - 1][x] == 1: 
      print(currentpath + "+" + str(x+1)) 
      newMatrix = adjMatrix 
      newMatrix[currentnode - 1][x] = 0 
      newMatrix[x][currentnode - 1] = 0 
      temp = currentpath 
      temp += str(x+1) 
      newpath = findPath(newMatrix, x+1,temp) 
      print(newpath) 
      if isFinished(newpath): 
       print ("Returning: " + newpath) 
       return newpath 
    return "" 


def isFinished(currentpath): 
    #Checks if node 1 is hit at least twice and each other node is hit at least once 
    if currentpath == "": 
     return False 

    for i in range(1, 9): 
     if i == 1 and currentpath.count(str(i)) < 2: 
      return False 
     elif currentpath.count(str(i)) < 1: 
      return False 
    #Checks if it starts and ends with 1 
    if not currentpath.startswith(str(1)) or not currentpath.endswith(str(1)): 
     return False 
    return True 

#This part is using only for self-testing 
if __name__ == "__main__": 
    def check_solution(func, teleports_str): 
     route = func(teleports_str) 
     teleports_map = [tuple(sorted([int(x), int(y)])) for x, y in teleports_str.split(",")] 
     if route[0] != '1' or route[-1] != '1': 
      print("The path must start and end at 1") 
      return False 
     ch_route = route[0] 
     for i in range(len(route) - 1): 
      teleport = tuple(sorted([int(route[i]), int(route[i + 1])])) 
      if not teleport in teleports_map: 
       print("No way from {0} to {1}".format(route[i], route[i + 1])) 
       return False 
      teleports_map.remove(teleport) 
      ch_route += route[i + 1] 
     for s in range(1, 9): 
      if not str(s) in ch_route: 
       print("You forgot about {0}".format(s)) 
       return False 
     return True 

    assert check_solution(checkio, "13,14,23,25,34,35,47,56,58,76,68"), "Fourth" 

Answer 1

Линия

newMatrix = adjMatrix 

просто создает другую ссылку на свой список. Вам нужно будет создать новый объект списка. Так как это матрица, сделайте это для содержимого:

newMatrix = [row[:] for row in adjMatrix] 

Это создает новый список копий ваших вложенных списков.