Возвращение в рекурсивный лабиринт; python

Question

Я кодирую алгоритм решения лабиринта, и у меня возникают проблемы с возвратом после того, как вы попали в «стену»

Пока что у меня есть код, который проверяет некоторые базовые c рекурсивные случаи, такие как если я достиг конца или если я проверил все пункты. Я также сделал так, что есть список, который отслеживает «путь» решения и соответственно добавляет и удаляет точки. Поэтому каждый раз, когда он добавляет точку, он проверяет, является ли она действительной, и проверяет точку выше, слева, справа и ниже et c. Если ни один из них не действителен, то этот оператор выполняется

    else:
    path.pop()
    return solve_maze(maze,path,end) 

, это удаляет точку и возвращает ее назад и проверяет следующие условия в начале функции.

square = list(path[-1])

#Base Case

if end in path:
    return True

elif square == None:
    return False

elif maze[square[0]][square[1]] == "X":
    path.pop()
    return solve_maze(maze,path,end)

elif tuple(square) in path:
    path.pop()
    return solve_maze(maze,path,end)

Однако, когда я выполняю последнюю строку, он просто удаляет все точки на моем пути, и я получаю ошибку индексации.

Любые советы о том, как я могу вернуться, как только я нажму тупик?

Answer 1

Вот решение с сильными комментариями:

def backtrack(i,j):
   # if matrix[i][j] is visited, then do nothing
   # if it is a wall, then do not insert it in the path from the first place
   if visit[i][j] != 0 or matrix[i][j] == 'X':
      return
   # mark the index as visited as to not visit it again
   visit[i][j] = 1
   # add the index to the path
   path.append((i,j))
   # if it is the GOAL, then store this path somewhere, 
   # and pop the last index to traverse other paths that reaches the GOAL
   if matrix[i][j] == 'G':
      # any paths that reach the GOAL are appended here
      ans.append(list(path))
      path.pop()
      return
   # loop on the neighbors. if they are valid indices, do the same work again
   for k in range(3):
      nwi = i + row[k]
      nwj = j + col[k]
      if valid(nwi, nwj):
         backtrack(nwi, nwj)
   # after finishing this index, just pop because we do not need it any more
   path.pop()
   return

def valid(i,j):
   return (i >= 0 and i <=2) and (j >= 0 and j <= 2)

# just a dummy matrix to start with
matrix = [['.', '.', '.'], ['.', 'X', '.'], ['.', 'G', 'X']]
# an array that marks indices as visited or not
visit = [[0,0,0],[0,0,0],[0,0,0]]
# the path that is used in the back tracking
path = []
# this will be a list of lists containing ALL the paths that can reach the GOAL
ans = []
# these are the neighbors indices
row = [-1, 1, 0, 0]
col = [0, 0, 1, -1]

backtrack(0,0)

if len(ans) == 0: 
   print("no path found!")
else:
   print(ans)

Мое решение предоставит вам все пути, которые могут достичь вашей цели, в списке списков под названием ans . Если длина ans равна нулю, пути не найдены.

Если вы не поняли комментарии, написанные в коде, или каким-либо образом запутались, не стесняйтесь комментировать, и я отвечу.

ПРИМЕЧАНИЕ: (редактировать)

Я предположил начальные состояния лабиринта и самого содержимого функции, потому что вы этого не сделали предоставьте любые контрольные примеры или всю вашу функцию.