Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

# What is the maze problem?

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 matrixN = 4# check is position is valid to movedef 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 