What is the maze problem?

First, we generate the corresponding matrix of the maze. White represents the area where the rat can travel and is represented by 1. Grey represents the area where the rat cannot go and is represented by 0.

{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}

For the given maze the path above should ideally be good to go from beginning to end.

To solve the maze problem, the program is required to generate the following matrix, where 1 represents the path taken by the rat to travel from source to destination.

{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}

Now, we all must be thinking, “how does a program interpret what path to take, where to move, or what happens in case of a dead-end?”

Well, the answer is easy – it uses an approach called the Backtracking Algorithm. Backtracking is an algorithmic technique used to recursively solve problems by trying to build a solution incrementally.

The program is solved one step at a time.

In the example below, we will be adopting this backtracking recursive approach. The example will follow a path and always keep a check if a destination is reached. If yes, a result will be returned. If No, it will backtrack to explore other paths.

Solution

Firstly, create a matrix to store your solution. It should contain all zeros and should be of the same size as the maze matrix.
Make a recursive call with the position of the rat in the matrix:

initial maze matrix
solution matrix

If the position provided is invalid, return from the function.
Otherwise, mark the position as 1 in the solution matrix.
Recursively call for position (i+1, j), (i, j+1), (i-1, j), and (i, j-1).

# size of maze matrix
N = 4
# check is position is valid to move
def checkpos(maze, x, y ):
    if x >= 0 and x < N:
        if y >= 0 and y < N:
            if maze[x][y] == 1:
                return True
     
    return False
 
def Helper(maze):
    # solution matrix
    sol = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
    ]
     
    if mazesolver(maze, 0, 0, sol) == False:
        return False
     
    for i in sol:
        for j in i:
            print(str(j) + " ", end ="")
        print("")
    return True
     
def mazesolver(maze, x, y, sol):
    # if destination reached
    if x == N - 1 and y == N - 1 and maze[x][y]== 1:
        sol[x][y] = 1
        return True
         
    # Check if position is valid
    if checkpos(maze, x, y) == True:
        if sol[x][y] == 1:
            return False
           
        sol[x][y] = 1
         
        # forward direction
        if mazesolver(maze, x + 1, y, sol) == True:
            return True
             
        # 
        # if above doesnt work, move in down direction
        if mazesolver(maze, x, y + 1, sol) == True:
            return True
           
        
        # if above two do not work, move back in left direction. Backtrack
        if mazesolver(maze, x - 1, y, sol) == True:
            return True
             
        # Else, move upwards
        if mazesolver(maze, x, y - 1, sol) == True:
            return True
         
        # if nothing works, backtrack and set the pos to 0 as we
        # will not be using the path. 
        sol[x][y] = 0
        return False
 
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
    ]
            
Helper(maze)

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

What is the maze problem?

What is the rat maze problem?

Solution