What is Rat in A maze Problem?
In this problem the Maze is described by the NxN binary matrix of the blocks where the source block is the upper leftmost block that is the maze[0][0] and destination block is always lower at the rightmost block that is the maze at [N-1][N-1]. A rat starts from source point and has to reach the desired destination. The rat can move only in two directions i.e forward and down.
In the maze matrix, 0 means the block is the dead end and 1 means the block that can be used in the path from source to destination. Note that this is a simple version for the typical Maze problem.
Image Reference: Geeks for Geeks
Rat in A maze Problem Flowchart:
Image Reference: Geeks for Geeks
Pseudocode for Rat in A maze Problem:
isValid(x, y)
Input: x and y point in the maze.
Output: True if the path (x,y) place is valid, otherwise false.
Begin
if x and y are in range and (x,y) place is not blocked, then
return true
return false
End
solveRatMaze(x, y)
Input: The starting point x and y.
Output: The path to be followed by the rat to reach the destination, otherwise false.
Begin
if (x,y) is the bottom right corner, then
mark the place as 1
return true
if isValidPlace(x, y) = true, then
mark (x, y) place as 1
/* For the forward movement*/ if solveRatMaze(x+1, y) = true, then
return true
/*For the downward movement */ if solveRatMaze(x, y+1) = true, then
return true
mark (x,y) as 0 when backtracks
return false
return false
End
Rat in A maze Problem Implementation in Java
public class RatMaze {
// Size of the maze
static int N;
/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
/* loop iterates */ for (int i = 0; i < N; i++) {
/* loop iterates */ for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] + " ");
System.out.println();
}
}
boolean isSafe(int maze[][], int x, int y)
{
// if (x, y outside maze) return false
/* condition */ return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
boolean solveMaze(int maze[][])
{
int sol[][] = new int[N][N];
if (solveMazeUtil(maze, 0, 0, sol) == false) {
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x, y is goal) return true
/*Check Condition */ if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true) {
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
RatMaze rat = new RatMaze();
/*Double Dimmensional Array */ int maze[][] = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 } };
N = maze.length;
rat.solveMaze(maze);
}
}
Output:
The 1 values show the path for rat
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1