Rat in A Maze Problem Algorithm and Flowchart

(1834 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.

Rat in A maze Problem

Image Reference: Geeks for Geeks

Rat in A maze Problem Flowchart:

Rat in A maze Problem flowhart

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

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search

Play 2048 Game Online

Play Duckhunt Online

Need Help?

Looking for any Software or Tutorial?
Don't Worry, we will find it for you
Contact Now

Search Tags

    Flowchart for Rat in A Maze Problem

    Java Program for Rat in a maze problem