# Rat in A Maze Problem Algorithm and Flowchart

(1308 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 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