Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

What is the maze problem?

Sarvech Qadir

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

You may remember the maze game from childhood where a player starts from one place and ends up at another destination via a series of steps. This game is also known as the rat maze problem.

What is the rat maze problem?

A rat starts at a position (source) and can only move in two directions:

  1. Forward
  2. Down

The goal is to reach the destination.

In computer science, we can solve the maze game using array indexes or the maze matrix.

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

  1. Firstly, create a matrix to store your solution. It should contain all zeros and should be of the same size as the maze matrix.

  2. Make a recursive call with the position of the rat in the matrix:

  • initial maze matrix
  • solution matrix
  1. If the position provided is invalid, return from the function.

  2. Otherwise, mark the position as 1 in the solution matrix.

  3. 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)

RELATED TAGS

python
communitycreator

CONTRIBUTOR

Sarvech Qadir
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring