Rat in a Maze Problem
The rat in a maze problem is a path finding puzzle in which our objective is to find an optimal path from a starting point to an exit point. In this puzzle, there is a rat which is trapped inside a maze represented by a square matrix. The maze contains different cells through which that rat can travel in order to reach the exit of maze.
Rat in a Maze Problem using Backtracking Approach
Suppose the maze is of size NxN, where cells can either be marked as 1 or 0. A cell marked as 1 indicates a valid path, whereas a cell marked as 0 indicates a wall or blocked cell. Remember, the rat can move in up, down, left, or right directions, but it can only visit each cell once. The source and destination locations are the top-left and bottom-right cells, respectively.
The goal is to find all possible paths for the rat to reach the destination cell (N-1, N-1) from the starting cell (0, 0). The algorithm will display a matrix, from which we can find the path of the rat to reach the destination point. The figure below illustrates the path −
The backtracking process systematically explores all possible paths by marking visited cells and backtracking from dead ends. This approach guarantees to find all possible solutions if they exist for the given problem.
To solve the rat in a maze problem using the backtracking approach, follow the below steps −
First, mark the starting cell as visited.
Next, explore all directions to check if a valid cell exists or not.
If there is a valid and unvisited cell is available, move to that cell and mark it as visited.
If no valid cell is found, backtrack and check other cells until the exit point is reached.
Example
Following is the example illustrating how to solve the Rat in a Maze problem in various programming languages.
#include <stdio.h>
#define N 5
// Original maze
int maze[N][N] = {
{1, 0, 0, 0, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 1, 1, 1}
};
// To store the final solution of the maze path
int sol[N][N];
void showPath() {
printf("The solution maze:
");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%d ", sol[i][j]);
printf("
");
}
}
// Function to check if a place is inside the maze and has value 1
int isValidPlace(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return 1;
return 0;
}
int solveRatMaze(int x, int y) {
// When (x,y) is the bottom right room
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return 1;
}
// Check whether (x,y) is valid or not
if (isValidPlace(x, y)) {
// Set 1 when it is a valid place
sol[x][y] = 1;
// Find path by moving in the right direction
if (solveRatMaze(x + 1, y))
return 1;
// When the x direction is blocked, go for the bottom direction
if (solveRatMaze(x, y + 1))
return 1;
// If both directions are closed, there is no path
sol[x][y] = 0;
return 0;
}
return 0;
}
int findSolution() {
if (solveRatMaze(0, 0) == 0) {
printf("There is no path
");
return 0;
}
showPath();
return 1;
}
int main() {
findSolution();
return 0;
}
#include<iostream>
#define N 5
using namespace std;
// original maze
int maze[N][N] = {
{1, 0, 0, 0, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 1, 1, 1}
};
// to store the final solution of the maze path
int sol[N][N];
void showPath() {
cout << "The solution maze: " << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << endl;
}
}
// function to check place is inside the maze and have value 1
bool isValidPlace(int x, int y) {
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
return false;
}
bool solveRatMaze(int x, int y) {
// when (x,y) is the bottom right room
if(x == N-1 && y == N-1) {
sol[x][y] = 1;
return true;
}
//check whether (x,y) is valid or not
if(isValidPlace(x, y) == true) {
//set 1, when it is valid place
sol[x][y] = 1;
//find path by moving right direction
if (solveRatMaze(x+1, y) == true)
return true;
//when x direction is blocked, go for bottom direction
if (solveRatMaze(x, y+1) == true)
return true;
//if both are closed, there is no path
sol[x][y] = 0;
return false;
}
return false;
}
bool findSolution() {
if(solveRatMaze(0, 0) == false) {
cout << "There is no path";
return false;
}
showPath();
return true;
}
int main() {
findSolution();
}
import java.util.Arrays;
public class MazeSolverClass {
private static final int N = 5;
// Original maze
private static int[][] maze = {
{1, 0, 0, 0, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0},
{1, 1, 1, 1, 1}
};
// To store the final solution of the maze path
private static int[][] sol = new int[N][N];
// to display path
private static void showPath() {
System.out.println("The solution maze:");
for (int i = 0; i < N; i++) {
System.out.println(Arrays.toString(sol[i]));
}
}
// Function to check if a place is inside the maze and has value 1
private static boolean isValidPlace(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1;
}
private static boolean solveRatMaze(int x, int y) {
// When (x,y) is the bottom right room
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
// Check whether (x,y) is valid or not
if (isValidPlace(x, y)) {
// Set 1 when it is a valid place
sol[x][y] = 1;
// Find path by moving in the right direction
if (solveRatMaze(x + 1, y)) {
return true;
}
// When the x direction is blocked, go for the bottom direction
if (solveRatMaze(x, y + 1)) {
return true;
}
// If both directions are closed, there is no path
sol[x][y] = 0;
return false;
}
return false;
}
private static boolean findSolution() {
return solveRatMaze(0, 0);
}
// main method
public static void main(String[] args) {
if (findSolution()) {
showPath();
} else {
System.out.println("There is no path");
}
}
}
N = 5
# Original maze
maze = [
[1, 0, 0, 0, 0],
[1, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 1]
]
# To store the final solution of the maze path
sol = [[0] * N for _ in range(N)]
def showPath():
print("The solution maze:")
for row in sol:
print(*row)
def isValidPlace(x, y):
return 0 <= x < N and 0 <= y < N and maze[x][y] == 1
def solveRatMaze(x, y):
# When (x,y) is the bottom right room
if x == N - 1 and y == N - 1:
sol[x][y] = 1
return True
# Check whether (x,y) is valid or not
if isValidPlace(x, y):
# Set 1 when it is a valid place
sol[x][y] = 1
# Find path by moving in the right direction
if solveRatMaze(x + 1, y):
return True
# When the x direction is blocked, go for the bottom direction
if solveRatMaze(x, y + 1):
return True
# If both directions are closed, there is no path
sol[x][y] = 0
return False
return False
def findSolution():
if not solveRatMaze(0, 0):
print("There is no path")
return False
showPath()
return True
if __name__ == "__main__":
findSolution()
Output
The solution maze: 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1
