Find paths from corner cell to middle cell in maze in Python

In this tutorial, we will learn about how we can find paths from corner cell to middle cell in a square maze in Python. So first we need to understand which type of maze input we are giving. We are giving a 9 x 9 matrix which will contain integer numbers.

Now the rule is we will start from the upper corner and we will move in any direction (up, right, down, left). We have to move the steps which are written in the current box. Let suppose if the number is written is 3 then we are free to move 3 steps in any direction.

Our final goal is to reach the middle point and need to print the path that how we approached the goal.

So let us achieve the solution by using a Python code.

Path to the middle cell in a maze from corner cell in Python

maze = [
    [3, 5, 4, 4, 7, 3, 4, 6, 3],
    [6, 7, 5, 6, 6, 2, 6, 6, 2],
    [3, 3, 4, 3, 2, 5, 4, 7, 2],
    [6, 5, 5, 1, 2, 3, 6, 5, 6],
    [3, 3, 4, 3, 0, 1, 4, 3, 4],
    [3, 5, 4, 3, 2, 2, 3, 3, 5],
    [3, 5, 4, 3, 2, 6, 4, 4, 3],
    [3, 5, 1, 3, 7, 5, 3, 6, 4],
    [6, 2, 4, 3, 4, 5, 4, 5, 1]
]

m=int(len(maze)/2)

Now, this is a maze which we are using. m denotes half of the size of the square maze.

def printPath(maze, i, j, ans):
    if m == i and m == j:
        ans += "(" + str(i) + ", " + str(j) + ") -> MID"
        print(ans)
        return

    if maze[i][j] == 0:
        return

We will define printPath function in which we will pass the whole maze matrix i, and j (current positions), then a string named ans. If i and j are successfully reached to middle cell meaning at (4, 4) it will print the ans. It will get out of the program as it reaches the middle cell.

    k = maze[i][j]

    maze[i][j] = 0

    if j + k < len(maze):
        printPath(maze, i, j + k, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if i + k < len(maze):
        printPath(maze, i + k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if j - k > 0:
        printPath(maze, i, j - k, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if i - k > 0:
        printPath(maze, i - k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    maze[i][j] = k


printPath(maze, 0, 0, "")

Otherwise, we are storing the cell value in k. Then we will set that cell value to 0 as it is already visited. We will also add 4 if statements that are responsible for moving pointer in four possible directions. First, if the statement will check if there is space in the right direction then (i, j) will move in the right and again recursively check that if the goal is achieved or not then it will again perform the same action. Similarly other if statements will perform to go in different directions.

And finally, we will call the function in which we will give the upper left corner (0, 0) as the initial position and ans as the empty string.

Below is the full code for this tutorial.

maze = [
    [3, 5, 4, 4, 7, 3, 4, 6, 3],
    [6, 7, 5, 6, 6, 2, 6, 6, 2],
    [3, 3, 4, 3, 2, 5, 4, 7, 2],
    [6, 5, 5, 1, 2, 3, 6, 5, 6],
    [3, 3, 4, 3, 0, 1, 4, 3, 4],
    [3, 5, 4, 3, 2, 2, 3, 3, 5],
    [3, 5, 4, 3, 2, 6, 4, 4, 3],
    [3, 5, 1, 3, 7, 5, 3, 6, 4],
    [6, 2, 4, 3, 4, 5, 4, 5, 1]
]

m=int(len(maze)/2)
def printPath(maze, i, j, ans):
    if m == i and m == j:
        ans += "(" + str(i) + ", " + str(j) + ") -> MID"
        print(ans)
        return

    if maze[i][j] == 0:
        return

    k = maze[i][j]

    maze[i][j] = 0

    if j + k < len(maze):
        printPath(maze, i, j + k, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if i + k < len(maze):
        printPath(maze, i + k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if j - k > 0:
        printPath(maze, i, j - k, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    if i - k > 0:
        printPath(maze, i - k, j, ans + "(" + str(i) + ", " + str(j) + ") -> ")

    maze[i][j] = k


printPath(maze, 0, 0, "")

Output:

(0, 0) -> (0, 3) -> (0, 7) -> (6, 7) -> (6, 3) -> (3, 3) -> 
(3, 4) -> (5, 4) -> (5, 2) -> (1, 2) -> (1, 7) -> (7, 7) -> 
(7, 1) -> (2, 1) -> (2, 4) -> (4, 4) -> MID

 

Leave a Reply