在python中使用递归解决迷宫

Solving a maze using recursion in python

提问by MarissaLeigh

So, I have an assignment which asks me to solve a maze using recursion. I will post the assignment guidelines so you can see what I am talking about. The professor didn't explain recursion that much, he gave us examples of recursion, which I will post, but I was hoping someone might be able to give me a more in depth explanation of the recursion, and how I would apply this to solving a maze. I'm not asking for anyone to write the code, I'm just hoping some explanations would put me on the right path. Thank you to anyone who answers.

所以，我有一个作业要求我使用递归解决迷宫。我将发布作业指南，以便您了解我在说什么。教授没有对递归解释那么多，他给了我们递归的例子，我会贴出来，但我希望有人能给我更深入的递归解释，以及我如何应用它来解决一个迷宫。我不是要求任何人编写代码，我只是希望一些解释能让我走上正确的道路。感谢任何回答的人。

Here are the examples I have:

以下是我的例子：

    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

Here are the guidelines:

以下是指南：

You are going to create a maze crawler capable of solving any maze you give it with the power of recursion!

您将创建一个迷宫爬虫，能够通过递归的力量解决您给它的任何迷宫！

Question 1 - Loading the maze

问题 1 - 加载迷宫

Before you can solve a maze you will have to load it. For this assignment you will use a simple text format for the maze. You may use this sample maze or create your own.

在解决迷宫之前，您必须加载它。对于此作业，您将为迷宫使用简单的文本格式。您可以使用此示例迷宫或创建自己的迷宫。

Your objective for this question is to load any given maze file, and read it into a 2-dimensional list. E.g.: loadMaze("somemaze.maze") should load the somemaze.maze file and create a list like the following...

这个问题的目标是加载任何给定的迷宫文件，并将其读入二维列表。例如： loadMaze("somemaze.maze") 应该加载 somemaze.maze 文件并创建一个如下所示的列表......

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

Note that the lists have been stripped of all '\r' and '\n' characters. In order to make the next question simpler you may make this list a global variable.

请注意，列表已删除所有 '\r' 和 '\n' 字符。为了使下一个问题更简单，您可以将此列表设为全局变量。

Next write a function that prints out the maze in a much nicer format:

接下来编写一个函数，以更好的格式打印出迷宫：

E.g.,

例如，

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

Test your code with different mazes before proceeding.

在继续之前用不同的迷宫测试你的代码。

Question 2 - Preparing to solve the maze

问题 2 - 准备解决迷宫

Before you can solve the maze you need to find the starting point! Add a function to your code called findStart() that will search the maze (character-by-character) and return the x and y coordinate of the 'S' character. You may assume that at most one such character exists in the maze. If no 'S' is found in the maze return -1 as both the x and y coordinates.

在解决迷宫之前，您需要找到起点！向您的代码中添加一个名为 findStart() 的函数，该函数将搜索迷宫（逐个字符）并返回“S”字符的 x 和 y 坐标。您可以假设迷宫中至多存在一个这样的角色。如果在迷宫中没有找到“S”，则返回 -1 作为 x 和 y 坐标。

Test your code with the 'S' in multiple locations (including no location) before proceeding.

在继续之前，在多个位置（包括无位置）使用“S”测试您的代码。

Question 3 - Solving the maze!

问题 3 - 解决迷宫！

Finally, you are ready to solve the maze recursively! Your solution should only require a single method: solve(y,x)

最后，您已准备好递归解决迷宫！您的解决方案应该只需要一个方法：solve(y,x)

A single instance of the solve method should solve a single location in your maze. The parameters y and x are the current coordinates to be solved. There are a few things your solve method should accomplish. It should check if it is currently solving the location of the 'E'. In that case your solve method has completed successfully. Otherwise it should try to recursively solve the space to the right. Note, your method should only try to solve spaces, not walls ('#'). If that recursion doesn't lead to the end, then try down, then left, and up. If all that fails, your code should backtrack a step, and try another direction.

解决方法的单个实例应该解决迷宫中的单个位置。参数 y 和 x 是要求解的当前坐标。您的求解方法应该完成一些事情。它应该检查它当前是否正在解决“E”的位置。在这种情况下，您的求解方法已成功完成。否则它应该尝试递归地解决右边的空间。请注意，您的方法应该只尝试解决空间，而不是墙壁（'#'）。如果该递归没有导致结束，则尝试向下，然后向左和向上。如果一切都失败了，您的代码应该回溯一步，并尝试另一个方向。

Lastly, while solving the maze, your code should leave indicators of its progress. If it is searching to the right, the current location should have a '>' in place of the empty space. If searching down put a 'v'. If searching left '<', and if searching up '^'. If your code has to backtrack remove the direction arrow, and set the location back to a ' '.

最后，在解决迷宫时，您的代码应该留下进度指示器。如果它向右搜索，则当前位置应该有一个“>”代替空白区域。如果向下搜索，请输入“v”。如果搜索左'<'，如果搜索'^'。如果您的代码必须回溯，请删除方向箭头，并将位置设置回“ ”。

Once your maze is solved print out the maze again. You should a see step-by-step guide to walking the maze. E.g.,

一旦你的迷宫被解决了，再次打印出迷宫。您应该查看走迷宫的分步指南。例如，

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

S is at (1,1)

S 在 (1,1)

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

Test your code with different different start and end locations, and optionally over a variety of mazes.

使用不同的开始和结束位置测试您的代码，并可选择在各种迷宫中进行测试。

Here is the code I have so far: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]!= ' ')

回答by Hugh Bothwell

Recursion is actually a simple idea: to solve a problem, you shrink the problem by one step, then solve the reduced problem. This continues until you reach a "base problem" that you know how to solve completely. You return the base solution, then add to the solution returned at each step until you have the full solution.

递归实际上是一个简单的想法：要解决一个问题，将问题缩小一步，然后解决缩小的问题。这一直持续到您到达一个您知道如何完全解决的“基本问题”。您返回基本解决方案，然后添加到每个步骤返回的解决方案中，直到您获得完整的解决方案。

So to solve n!, we remember n and solve for (n-1)!. The base case is 1!, for which we return 1; then at each return step we multiply by the remembered number (2 * 1! is 2, 3 * 2! is 6, 4 * 3! is 24, 5 * 4! is 120) until we multiply by n and have the full solution. This is actually a pretty pale and anemic sort of recursion; there is only one possible decision at each step. Known as "tail recursion", this is very easy to turn inside-out and convert to an iterative solution (start at 1 and multiply by each number up to n).

所以为了求解 n!，我们记住 n 并求解 (n-1)!。基本情况是 1！，我们返回 1；然后在每个返回步骤我们乘以记住的数字（2 * 1！是 2，3 * 2！是 6，4 * 3！是 24，5 * 4！是 120）直到我们乘以 n 并得到完整的解决方案. 这实际上是一种相当苍白和贫血的递归；每一步只有一个可能的决定。被称为“尾递归”，这很容易由内而外转换并转换为迭代解决方案（从 1 开始，乘以每个数字直到 n）。

A more interesting sort of recursion is where you split the problem in half, solve each half, then combine the two half-solutions; for example quicksort sorts a list by picking one item, dividing the list into "everything smaller than item" and "everything bigger than item", quicksorting each half, then returning quicksorted(smaller) + item + quicksorted(larger). The base case is "when my list is only one item, it is sorted".

一种更有趣的递归是将问题分成两半，解决每一半，然后组合两个半解决方案；例如快速排序通过选择一个项目对列表进行排序，将列表分为“所有小于项目”和“所有大于项目”，快速排序每一半，然后返回快速排序（较小）+项目+快速排序（较大）。基本情况是“当我的列表只有一项时，它被排序”。

For the maze, we are going to split the problem four ways - all solutions possible if I go right, left, up, and down from my current location - with the special feature that only one of the recursive searches will actually find a solution. The base case is "I am standing on E", and a failure is "I am in a wall" or "I am on a space I have already visited".

对于迷宫，我们将把问题分成四种方式——如果我从当前位置向右、向左、向上和向下走，所有可能的解决方案——具有特殊功能，即只有一个递归搜索才能真正找到解决方案。基本情况是“我站在 E 上”，失败是“我在墙上”或“我在一个我已经访问过的空间”。

---

---

Edit:for interest's sake, here is an OO solution (compatible with both Python 2.x and 3.x):

编辑：出于兴趣，这里是一个面向对象的解决方案（与 Python 2.x 和 3.x 兼容）：

from collections import namedtuple

Dir = namedtuple("Dir", ["char", "dy", "dx"])

class Maze:
    START = "S"
    END   = "E"
    WALL  = "#"
    PATH  = " "
    OPEN  = {PATH, END}  # map locations you can move to (not WALL or already explored)

    RIGHT = Dir(">",  0,  1)
    DOWN  = Dir("v",  1,  0)
    LEFT  = Dir("<",  0, -1)
    UP    = Dir("^", -1,  0)
    DIRS  = [RIGHT, DOWN, LEFT, UP]

    @classmethod
    def load_maze(cls, fname):
        with open(fname) as inf:
            lines = (line.rstrip("\r\n") for line in inf)
            maze  = [list(line) for line in lines]
        return cls(maze)

    def __init__(self, maze):
        self.maze = maze

    def __str__(self):
        return "\n".join(''.join(line) for line in self.maze)

    def find_start(self):
        for y,line in enumerate(self.maze):
            try:
                x = line.index("S")
                return y, x
            except ValueError:
                pass

        # not found!
        raise ValueError("Start location not found")

    def solve(self, y, x):
        if self.maze[y][x] == Maze.END:
            # base case - endpoint has been found
            return True
        else:
            # search recursively in each direction from here
            for dir in Maze.DIRS:
                ny, nx = y + dir.dy, x + dir.dx
                if self.maze[ny][nx] in Maze.OPEN:  # can I go this way?
                    if self.maze[y][x] != Maze.START: # don't overwrite Maze.START
                        self.maze[y][x] = dir.char  # mark direction chosen
                    if self.solve(ny, nx):          # recurse...
                        return True                 # solution found!

            # no solution found from this location
            if self.maze[y][x] != Maze.START:       # don't overwrite Maze.START
                self.maze[y][x] = Maze.PATH         # clear failed search from map
            return False

def main():
    maze = Maze.load_maze("somemaze.txt")

    print("Maze loaded:")
    print(maze)

    try:
        sy, sx = maze.find_start()
        print("solving...")
        if maze.solve(sy, sx):
            print(maze)
        else:
            print("    no solution found")
    except ValueError:
        print("No start point found.")

if __name__=="__main__":
    main()

and when run produces:

当运行产生：

Maze loaded:
    ####################################
    #S#  ##  ######## # #      #     # #
    # #   #             # #        #   #
    #   # ##### ## ###### # #######  # #
    ### # ##    ##      # # #     #### #
    #   #    #  #######   #   ###    #E#
    ####################################
solving...
    ####################################
    #S#  ##  ######## # #>>>>>v#  >>v# #
    #v#>>v#    >>>v     #^#   >>>>^#>>v#
    #>>^#v#####^##v######^# #######  #v#
    ### #v##>>>^##>>>>>v#^# #     ####v#
    #   #>>>^#  #######>>^#   ###    #E#
    ####################################

Note that the assignment as given has a few unPythonic elements:

请注意，给定的赋值有一些非 Pythonic 元素：

• it asks for camelCasefunction names rather than underscore_separated
• it suggests using a global variable rather than passing data explicitly
• it asks for find_startto return flag values on failure rather than raising an exception

• 它要求提供camelCase函数名称而不是underscore_separated
• 它建议使用全局变量而不是显式传递数据
• 它要求find_start在失败时返回标志值而不是引发异常

回答by EdwinW

(Dating myself, I actually did this problem in COBOL, in high-school.)

（与自己约会，实际上我在高中时在 COBOL 中做过这个问题。）

You can think of solving the maze as taking steps.

您可以将解决迷宫视为采取步骤。

When you take a step, the same rules apply every time. Because the same rules apply every time, you can use the exact same set of instructions for each step. When you take a step, you just call the same routine again, changing the parameters to indicate the new step. That's recursion. You break the problem down by taking it one step at a time.

当您迈出一步时，每次都适用相同的规则。由于每次都适用相同的规则，因此您可以对每个步骤使用完全相同的指令集。当您迈出一步时，您只需再次调用相同的例程，更改参数以指示新的步骤。这就是递归。您可以通过一次一个步骤来分解问题。

Note: Some recursion solutions break the problem in half, solving each half independent of the other, that works when the two solutions are actually independent. It doesn't work here because each step (solution) depends on the previous steps.

注意：一些递归解决方案将问题分成两半，解决每一半独立于另一半，这在两个解决方案实际上是独立的时有效。它在这里不起作用，因为每个步骤（解决方案）都取决于前面的步骤。

If you hit a dead end, you back out of the dead end, until you find a step where there are still viable squares to check.

如果您遇到死胡同，您就会退出死胡同，直到您找到一个步骤，在那里仍然可以检查可行的方格。

Helpful Hint: You don't mark the correct path on the way tothe exit, because you don't know that the step you're taking right now is part of the path to the exit. You mark the path on the way back, when you know that each step is indeed part of the path. You can do this because each step remembers which square it was in before it took the next step.

Instead, you put a mark in each square you've tried that only says: I've been here, no need to check this one again. Clean those up before you print the solution.

提示：您没有标记的道路上正确的路径到退出，因为你不知道你现在正在采取步骤是通向出口的一部分。当您知道每一步确实是路径的一部分时，您就可以在返回的路上标记路径。您可以这样做，因为每一步都会记住它在进行下一步之前所在的方格。

相反，你在你尝试过的每个方格上做一个标记，只说：我来过这里，不需要再检查这个。在打印解决方案之前清理它们。

回答by sabbahillel

Maze solving with pythonshows my answer. However, if you want to do the code yourself the steps are.

用python解决迷宫显示了我的答案。但是，如果您想自己编写代码，步骤是。

 1. Start at the entrance.  
 2. Call the function solve(x,y) with the entrance co-ordinates  
 3. in solve, return false if the input point has already been handled or is a wall.  
 4. Mark the current point as handled (tag = 'o')  
 5. go to the right and call solve on that point. If it returns true, set tag to '>'  
 6 elif do the same for left and '<'  
 7 elif do the same for up and '^'  
 8 elif do the same for down and 'v'  
 9 else this is a false path, set tag = ' ' 
10 set the current maze point to tag
11 return (tag != ' ')

Alternatively leave step 9 out and make step 11

或者省略第 9 步并进行第 11 步

return(tag != 'o')

Then search through the maze and replace every 'o' with ' '

然后在迷宫中搜索并将每个 'o' 替换为 ' '

You can display the maze both ways so that it will show how you tried to solve it as well as the final answer. This has been used as a Solaris screensaver with the potential paths showing in one color and the actual path in a different color so that you can see it trying and then succeeding.

您可以以两种方式显示迷宫，以便它显示您如何尝试解决它以及最终答案。这已被用作 Solaris 屏幕保护程序，其中潜在路径以一种颜色显示，实际路径以不同颜色显示，以便您可以看到它尝试然后成功。

回答by Igor Pomaranskiy

Here is my solution of CodeEval's The Labirynthchallenge:

这是我对 CodeEval 的The Labirynth挑战的解决方案：

import sys
sys.setrecursionlimit(5000)


class Maze(object):
    FLOOR = ' '
    WALLS = '*'
    PATH = '+'

    def __init__(self):
        self.cols = 0
        self.rows = 0
        self.maze = []

    def walk_forward(self, current_k, r, c):
        self.maze[r][c] = current_k
        next_k = current_k + 1
        # up
        if r > 1:
            up = self.maze[r - 1][c]
            if up != self.WALLS:
                if up == self.FLOOR or int(up) > current_k:
                    self.walk_forward(next_k, r - 1, c)
        # down
        if r < self.rows - 1:
            down = self.maze[r + 1][c]
            if down != self.WALLS:
                if down == self.FLOOR or int(down) > current_k:
                    self.walk_forward(next_k, r + 1, c)
        # left
        if c > 1:
            left = self.maze[r][c - 1]
            if left != self.WALLS:
                if left == self.FLOOR or int(left) > current_k:
                    self.walk_forward(next_k, r, c - 1)
        # right
        if c < self.cols - 1:
            right = self.maze[r][c + 1]
            if right != self.WALLS:
                if right == self.FLOOR or int(right) > current_k:
                    self.walk_forward(next_k, r, c + 1)

    def walk_backward(self, r, c):
        current_k = self.maze[r][c]
        if not isinstance(current_k, int):
            return False
        self.maze[r][c] = self.PATH

        up = self.maze[r - 1][c] if r > 0 else None
        down = self.maze[r + 1][c] if r < self.rows - 1 else None
        left = self.maze[r][c - 1] if c > 1 else None
        right = self.maze[r][c + 1] if c < self.cols else None

        passed = False
        if up and isinstance(up, int) and up == current_k - 1:
            self.walk_backward(r - 1, c)
            passed = True
        if down and isinstance(down, int) and down == current_k - 1:
            self.walk_backward(r + 1, c)
            passed = True
        if left and isinstance(left, int) and left == current_k - 1:
            self.walk_backward(r, c - 1)
            passed = True
        if right and isinstance(right, int) and right == current_k - 1:
            self.walk_backward(r, c + 1)                    

    def cleanup(self, cleanup_path=False):
        for r in range(0, self.rows):
            for c in range(0, self.cols):
                if isinstance(self.maze[r][c], int):
                    self.maze[r][c] = self.FLOOR
                if cleanup_path and self.maze[r][c] == self.PATH:
                    self.maze[r][c] = self.FLOOR

    def solve(self, start='up', show_path=True):
        # finding start and finish points
        upper = lower = None
        for c in range(0, self.cols):
            if self.maze[0][c] == self.FLOOR:
                upper = (0, c)
                break
        for c in range(0, self.cols):
            if self.maze[self.rows - 1][c] == self.FLOOR:
                lower = (self.rows - 1, c)
                break
        if start == 'up':
            start = upper
            finish = lower
        else:
            start = lower
            finish = upper

        self.cleanup(cleanup_path=True)
        self.walk_forward(1, start[0], start[1])
        length = self.maze[finish[0]][finish[1]]
        if not isinstance(length, int):
            length = 0
        if show_path:
            self.walk_backward(finish[0], finish[1])
            self.cleanup(cleanup_path=False)
        else:
            self.cleanup(cleanup_path=True)
        return length

    def save_to_file(self, filename):
        with open(filename, 'w') as f:
            f.writelines(str(self))

    def load_from_file(self, filename):
        self.maze = []
        with open(filename, 'r') as f:
            lines = f.readlines()
        for line in lines:
            row = []
            for c in line.strip():
                row.append(c)
            self.maze.append(row)
        self.rows = len(self.maze)
        self.cols = len(self.maze[0]) if self.rows > 0 else 0

    def get_maze(self):
        return copy.copy(self.maze)

    def __str__(self):
        as_string = u''
        for row in self.maze:
            as_string += u''.join([str(s)[-1] for s in row]) + "\n"
        return as_string


maze = Maze()
maze.load_from_file(sys.argv[1])
maze.solve(show_path=True)
print str(maze)

回答by u10206492

This is the code I worte earlier, may be useful to you

这是我之前写的代码，可能对你有用

check the full code here:https://github.com/JK88-1337/MazeSolve

在此处查看完整代码：https: //github.com/JK88-1337/MazeSolve

#import part
import time
import sys
import os

#global values
load = 0                                 # set initial loading value
walk = [(1,0),(-1,0),(0,1),(0,-1)]       # set movements
backtracker = []                         # set backtracker (remember that this is a stack)
gmainmaze = []                           # set initial blank maze

def initialize():   #loading 
    sx = 0 # start x value
    sy = 0 # start y value
    ex = 0 # end x value
    ey = 0 # end y value
    while load == 0:    #just some cool animation
        sys.stdout.write("\rloading |")
        time.sleep(0.1)
        sys.stdout.write("\rloading /")
        time.sleep(0.1)
        sys.stdout.write("\rloading -")
        time.sleep(0.1)
        sys.stdout.write("\rloading \")
        time.sleep(0.1)
        sys.stdout.write("\r")
        mainmaze = loadMaze("maze.txt") # IMPORTANT: load the maze under the same folder named "maze.txt"
        print("Maze Loaded")
        print(" ")
        time.sleep(1)
        print(" ")
        print("Locating start point...")
        sx, sy = spotter(5,mainmaze)
        time.sleep(1)
        print(" ")
        print("Locating end point...")
        ex, ey = spotter(3,mainmaze)
        print(" ")
        time.sleep(1)
        return sx, sy, ex, ey, mainmaze;
        break
    print(" ")
    sys.stdout.write("\rInitialized!")
    print(" ")
    time.sleep(3)
    os.system("cls")

def loadMaze(filename):
    #load the data from the file into a 2D list
    with open(filename) as i:
        maze = []
        for line in i:
            line = line.strip()
            spawnmaze = line.split(", ")
            maze.append(spawnmaze)
    return maze

def spotter(num,maze):
    #Locate the 'element' in the maze (this can either be "5" or "3")
    num = str(num)
    rowcounter = -1
    linecounter = 0
    for rows in maze:
        rowcounter = rowcounter + 1
        if num in rows:
            for element in rows:
                if element == num:
                    print("Tango Spotted, Grid:", rowcounter, linecounter)
                    return rowcounter, linecounter;
                    break
                linecounter = linecounter + 1

def valid(maze,x,y): # check if valid
    height = len(maze) - 1
    width = len(maze[0]) - 1
    if 0 <= x <= height and 0 <= y <= width:
        return 1
    else: 
        return 0

def solveMaze(sx,sy,ex,ey): # solve maze
    global gmainmaze
    for i in walk:          #try every direction
        x = sx + i[0]       #make the move
        y = sy + i[1]
        if valid(gmainmaze,x,y): # check if still in the maze
            if x == ex and y == ey: #check if reached destination
                print("SITREP:Destination Arrived")
                print("The Logistic Path Is:\n",backtracker)
                print(" ")
                return 1
            else:
                if gmainmaze[x][y] == "0" and (x,y) not in backtracker: #add to the stack
                    backtracker.append((x,y))
                else:
                    continue
        else:
            continue
        if solveMaze(x,y,ex,ey) == 1: # Recursion (do the next step)
            return 1
        else:
            continue
    go = backtracker.pop(-1) #moveback while 
    return 0

def printMaze(maze):
    for x in range(len(maze)):
        for y in range(len(maze[x])):
            print(maze[x][y], end=' ')
        print("")

def visualize(maze):    # a cool function to visualize the maze
    for x in range(len(maze)):
        for y in range(len(maze[x])):
            if maze[x][y] == "5":
                maze[x][y] = "╳"    # path
            elif maze[x][y] == "0":
                maze[x][y] = "?"    # unbeen path
            elif maze[x][y] == "1":
                maze[x][y] = "█"    # wall
            elif maze[x][y] == "3":
                maze[x][y] = "╳"    # basically path as well
            print(maze[x][y], end=' ')
        print("")


def main():
    #initialize the maze
    sx, sy, ex, ey, mainmaze = initialize()
    global gmainmaze
    gmainmaze = mainmaze
    load = 1
    #solve the maze
    gmainmaze[sx][sy] = "0"
    gmainmaze[ex][ey] = "0" # change the start and end into "0" to make it a way
    solveMaze(sx,sy,ex,ey)
    for i in backtracker:
        gmainmaze[i[0]][i[1]] = "5"
    gmainmaze[sx][sy] = "5"
    gmainmaze[ex][ey] = "3" # change the start and end back
    #print the maze
    width = len(gmainmaze[0]) - 1
    print("Check Your Map...")
    print("Map:")
    print("--"*(width+1))
    printMaze(gmainmaze)
    print("--"*(width+1))
    #visualize the maze uncomment to establish the function (btw check if your terminal can print these unicodes)
    #visualize(gmainmaze)
    time.sleep(5)

main()
? 2020 GitHub, Inc.