Hướng dẫn recursive maze solver python - python giải mê cung đệ quy

Vì vậy, tôi có một bài tập yêu cầu tôi giải quyết một mê cung bằng cách sử dụng đệ quy. Tôi sẽ đăng các hướng dẫn chuyển nhượng để bạn có thể thấy những gì tôi đang nói. Giáo sư đã không giải thích đệ quy nhiều như vậy, ông đã cho chúng tôi các ví dụ về đệ quy, mà tôi sẽ đăng, nhưng tôi đã hy vọng ai đó có thể cho tôi một lời giải thích sâu hơn về đệ quy, và cách tôi sẽ áp dụng điều này để giải quyết một mê cung. Tôi không yêu cầu ai viết mã, tôi chỉ hy vọng một số lời giải thích sẽ đưa tôi đi đúng hướng. Cảm ơn bất cứ ai trả lời.

Đây là những ví dụ tôi có:

    def foo():
        print("Before")
        bar()
        print("After")

    def bar():
        print("During")


    def factorial(n):
        """n!"""
        product = 1
        for i in range(n,0,-1):
        product *= i
        return product

    def recFac(n):
        """n! = n * (n-1)!"""
        if(n == 1):
          return 1
        return n * recFac(n-1)

    def hello():
        """Stack overflow!"""
        hello()

    def fib(n):
        """f(n) = f(n-1) + f(n-2)
        f(0) = 0
        f(1) = 1"""
        if n == 0 or n == 1: #base case
           return n
        return fib(n-1) + fib(n-2) #recursive case

    def mult(a,b):
        """a*b = a + a + a + a ..."""
        #base case
        if (b == 1):
           return a
        #recursive case
        prod = mult(a,b-1)
        prod *= a
        return prod


    def exp(a,b):
        """a ** b = a* a * a * a * a *.... 'b times'"""
        #base case
        if (b==0):
           return 1
        if (b == 1):
           return a
        #recursive case
        return exp(a,b-1)*a

    def pallindrome(word):
        """Returns True if word is a pallindrome, False otherwise"""
        #base case
        if word == "" or len(word)==1:
           return True

        #recursive case
        if word[0] == word[len(word)-1]:
        word = word[1:len(word)-1]
        return pallindrome(word)
        else:
            return False

Đây là các hướng dẫn:

Bạn sẽ tạo ra một trình thu thập dữ liệu mê cung có khả năng giải quyết bất kỳ mê cung nào bạn đưa ra với sức mạnh của đệ quy!

Câu 1 - Đang tải mê cung

Trước khi bạn có thể giải quyết một mê cung, bạn sẽ phải tải nó. Đối với bài tập này, bạn sẽ sử dụng một định dạng văn bản đơn giản cho mê cung. Bạn có thể sử dụng mê cung mẫu này hoặc tạo ra của riêng bạn.

Mục tiêu của bạn cho câu hỏi này là tải bất kỳ tệp mê cung nhất định nào và đọc nó vào danh sách 2 chiều. Ví dụ: loadmaze ("somemaze.maze") nên tải tệp somemaze.maze và tạo một danh sách như sau ...

    [['#','#','#','#','#','#','#','#','#'], 
     ['#','S','#',' ',' ',' ','#','E','#'], 
     ['#',' ','#',' ','#',' ',' ',' ','#'], 
     ['#',' ',' ',' ','#',' ','#',' ','#'], 
     ['#', #','#','#','#','#','#','#','#']] 

Lưu ý rằng các danh sách đã bị tước tất cả các ký tự '\ r' và '\ n'. Để làm cho câu hỏi tiếp theo đơn giản hơn, bạn có thể biến danh sách này thành một biến toàn cầu.

Tiếp theo viết một chức năng in ra mê cung ở định dạng đẹp hơn nhiều:

E.g.,

    ####################################
    #S#  ##  ######## # #      #     # #
    # #   #             # #        #   #
    #   # ##### ## ###### # #######  # #
    ### # ##    ##      # # #     #### #
    #   #    #  #######   #   ###    #E#
    ####################################

Kiểm tra mã của bạn với các mê cung khác nhau trước khi tiến hành.

Câu 2 - Chuẩn bị giải quyết mê cung

Trước khi bạn có thể giải quyết mê cung bạn cần tìm điểm xuất phát! Thêm một hàm vào mã của bạn gọi là findStart () sẽ tìm kiếm mê cung (ký tự từng ký tự) và trả về tọa độ x và y của ký tự 'S'. Bạn có thể cho rằng nhiều nhất là một nhân vật như vậy tồn tại trong mê cung. Nếu không có 's' nào được tìm thấy trong Mê cung trở lại -1 là cả tọa độ X và Y.

Kiểm tra mã của bạn với 'S' ở nhiều vị trí (bao gồm không có vị trí) trước khi tiến hành.

Câu 3 - Giải quyết mê cung!

Cuối cùng, bạn đã sẵn sàng để giải quyết mê cung đệ quy! Giải pháp của bạn chỉ cần yêu cầu một phương pháp duy nhất: Giải (Y, X)

Một trường hợp duy nhất của phương thức giải quyết sẽ giải quyết một vị trí duy nhất trong mê cung của bạn. Các tham số y và x là các tọa độ hiện tại cần giải quyết. Có một vài điều mà phương pháp giải quyết của bạn nên hoàn thành. Nó nên kiểm tra xem nó hiện đang giải quyết vị trí của 'E'. Trong trường hợp đó, phương pháp giải quyết của bạn đã hoàn thành thành công. Nếu không, nó nên cố gắng giải quyết đệ quy không gian sang phải. Lưu ý, phương thức của bạn chỉ nên cố gắng giải quyết không gian, không phải tường ('#'). Nếu đệ quy đó không dẫn đến kết thúc, thì hãy thử xuống, sau đó trái và lên. Nếu tất cả những điều đó thất bại, mã của bạn sẽ quay lại một bước và thử một hướng khác.

Cuối cùng, trong khi giải quyết mê cung, mã của bạn sẽ để lại các chỉ số về tiến trình của nó. Nếu nó đang tìm kiếm bên phải, vị trí hiện tại sẽ có '' 'thay cho không gian trống. Nếu tìm kiếm xuống, đặt một 'v'. Nếu tìm kiếm bên trái '

Khi mê cung của bạn được giải quyết, hãy in ra mê cung. Bạn nên xem hướng dẫn từng bước để đi bộ trong mê cung. Ví dụ.,

    main("somemaze.maze")
    ######### 
    #S#   #E# 
    # # #   # 
    #   # # # 
    #########

S ở (1,1)

     ######### 
     #S#>>v#E# 
     #v#^#>>^# 
     #>>^# # # 
     #########

Kiểm tra mã của bạn với các vị trí bắt đầu và kết thúc khác nhau, và tùy chọn qua nhiều mê cung.

Đây là mã tôi có cho đến nay: nhưng mã không thực sự in bản nhạc trong mê cung và tôi không chắc tại sao. But the code is not actually printing the track in the maze, and I'm not sure why.

    def loadMaze():
        readIt = open('Maze.txt', 'r')
        readLines = readIt.readlines()
        global mazeList
        mazeList = [list(i.strip()) for i in readLines]

    def showMaze():
        for i in mazeList:
            mazeprint = ''
        for j in i:
            mazeprint = mazeprint + j
        print(mazeprint)
        print('\n')    

    def solve(x,y, mazeList):
        mazeList[x][y] = "o"
        #Base case  
        if y > len(mazeList) or x > len(mazeList[y]):
           return False
        if mazeList[y][x] == "E":
           return True 
        if mazeList[y][x] != " ":
           return False
        #marking
        if solve(x+1,y) == True:  #right
           mazeList[x][y]= '>'
        elif solve(x,y+1) == True:  #down
             mazeList[x][y]= 'v'     
        elif solve(x-1,y) == True:  #left
             mazeList[x][y]= '<'     
        elif solve(x,y-1) == True:  #up
             mazeList[x][y]= '^'
        else:
           mazeList[x][y]= ' '
        return (mazeList[x][y]!= ' ')