python лабиринт с использованием рекурсии

Question

Я хочу решить лабиринт с помощью рекурсии. Программа открывает текстовый файл, как этот:

10 20 
1 1 
10 20 
----------------------------------------- 
|  |  | |  | | |  |  | | 
|-+ +-+-+ +-+ + +-+ + + +-+-+ +-+-+ + + | 
|   |  |  | | | | | | | 
| + +-+ + + +-+-+-+ + + + + + +-+ + + + | 
| | | |  |  | |  |  | | | 
| +-+-+-+-+ +-+ +-+-+-+-+ +-+ + +-+-+ +-| 
| | | |  | | |   | | | | 
| + + +-+ +-+-+ + + + +-+ +-+ + + + +-+ | 
|  |  | | |  | | | | | | | 
|-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+ +-+-+ +-| 
| | | |  |  |  | | | | | | 
| +-+-+ +-+-+ +-+ + +-+-+ +-+ +-+ + + + | 
|  |  | | | | | | | |  | 
|-+ +-+ + + +-+ +-+-+ + +-+ + + +-+ +-+ | 
| | | | |  | | | | | | | | | | | | 
|-+ + +-+ + + + + + +-+ + + + + +-+-+ + | 
|  | | | |  |  |    | 
| + + +-+ + +-+-+-+ + +-+ + + +-+-+ +-+ | 
| | |  | |   | | | |  | | 
----------------------------------------- 

первая строка файла является размер лабиринта (10 20), вторая линия является начальной точкой (1: 1), а третья линия это выход (10, 20). Я хочу отметить правильный путь с помощью «*». Вот как выглядит мой код:

EDIT: Я меняю код на findpath() funtion, и теперь я не получаю никаких ошибок, но лабиринт пуст, путь ('*') не «нарисован», на лабиринте.

class maze():  
    def __init__(self, file): 

     self.maze_list = [] 

     data= file.readlines() 

     size = data.pop(0).split() # size of maze 

     start = data.pop(0).split() # starting row and column; keeps being 0 because the previous not there anymore 
     self.start_i = start[0] # starting row 
     self.start_j = start[1] # starting column 

     exit = data.pop(0).split() # exit row and column 
     self.end_i = exit[0] 
     self.end_j = exit[1] 

     for i in data: 
      self.maze_list.append(list(i[:-1])) # removes \n character off of each list of list 
     print(self.maze_list) # debug 


    def print_maze(self): 

     for i in range(len(self.maze_list)): 
      for j in range(len(self.maze_list[0])): 
       print(self.maze_list[i][j], end='')       
      print() 

def main(): 

    filename = input('Please enter a file name to be processed: ') # prompt user for a file 


    try: 
     file = open(filename, 'r') 
    except:      # if a non-existing file is atempted to open, returns error 
     print("File Does Not Exist") 
     return 

    mazeObject = maze(file) 
    mazeObject.print_maze() # prints maze 

    row = int(mazeObject.start_i) 
    col = int(mazeObject.start_j) 

    findpath(row, col, mazeObject) # finds solution route of maze if any 

def findpath(row, col, mazeObject): 

    if row == mazeObject.end_i and col == mazeObject.end_j: # returns True if it has found the Exit of the maze 
     mazeObject.maze_list[row][col] = ' ' # to delete wrong path 
     return True 

    elif mazeObject.maze_list[row][col] == "|": # returns False if it finds wall 
     return False 

    elif mazeObject.maze_list[row][col] '-': # returns False if it finds a wall 
    return False 

    elif mazeObject.maze_list[row][col] '+': # returns False if it finds a wall 
     return False  

    elif mazeObject.maze_list[row][col] '*': # returns False if the path has been visited 
     return False 

    mazeObject.maze_list[row][col] = '*' # marks the path followed with an * 

    if ((findpath(row + 1, col, mazeObject)) 
     or (findpath(row, col - 1, mazeObject)) 
     or (findpath(row - 1, col, mazeObject)) 
     or (findpath(row, col + 1, mazeObject))): # recursion method 
     mazeObject.maze_list[row][col] = ' ' # to delete wrong path 
     return True 
    return False  

Итак, теперь мой вопрос: где ошибка? Я имею в виду, что программа просто распечатывает лабиринт без решения. Я хочу заполнить правильный путь «*».

Answer 1

Глядя на ваш код, я вижу несколько ошибок. Вы не правильно обрабатываете строки входа и выхода из строки/столбца. (10,20) является правильным для этого лабиринта, если вы предполагаете, что каждая другая строка и каждый другой столбец являются сеткой. То есть, если символы | и - представляют бесконечно тонкие линии, которые имеют случайные перерывы в них, подобно традиционным рисункам лабиринта.

Вам необходимо многократно разделить на две части и справиться с неизбежными ошибками fencepost, чтобы правильно перевести параметры вашего файла в значения столбца/столбца массива.

Далее ваша findpath функция спутать:

Во-первых, она должна быть методом класса. Он обращается к внутренним данным и содержит «внутренние знания» о деталях класса. Сделайте это методом!

Во-вторых, ваше условие выхода заменяет текущий символ пробелом «для удаления неправильного пути». Но если вы нашли выход, путь по определению правильный. Не делай этого!

В-третьих, у вас есть куча операторов if для разных типов символов. Это хорошо, но, пожалуйста, заменить их одним if заявления с использованием

if self.maze_list[row][col] in '|-+*': 
    return False 

В-четвертых, вы ждете, чтобы отметить текущую ячейку с «*», пока ваши чеки. Но вы должны отметить ячейку, прежде чем объявлять победу, когда вы достигнете места выхода. Думаю, переместите тест выхода.

Это должно хорошо очищать вещи.

В-пятых, и, наконец, ваш рекурсивный тест назад. Ваш код возвращает True, когда он достигнет выхода. Ваш код возвращает False, когда он бежит в стену или пытается пересечь собственный путь. Поэтому, если код принимает путь к мертвой точке, он достигнет конца, вернет false, разворачивает рекурсию несколько раз, возвращая ложь все время, пока он не вернется.

Таким образом, если вы ВСЕГДА видите возврат True, вы знаете, что код нашел выход по этому пути. Вы хотите немедленно вернуть true и сделать ничего больше. Конечно, не стирайте путь - это ведет к выходу!

С другой стороны, если ни одно из ваших возможных направлений не возвращает истину, то вы нашли тупик - выход не лежит в этом направлении.Вы должны удалить свой путь, верните False и надейтесь, что выход можно найти на более высоком уровне.