Rat in A Maze Problem Algorithm and Flowchart

[16569 views]

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); } }