Backtracking

Rat in a Maze

Pinterest LinkedIn Tumblr

A Maze is given matrix and Rat start from upper left and should reach to lower right. The Rat starts from source to destination and moves only forward and down direction.

Given a maze, 4 x 4 matrix. A rat has to find a path from source to destination. Rat start from left top corner and go to right bottom destination. There are few cells which are dead end which means rat cannot enter into those cells.

Write a program to rat start from source to destination?

source Code

package com.dsacode.Algorithm.backtracking;
 
import java.util.Arrays;
 
public class RatinMaze {
      
    public int[][] solution;
  
    public RatinMaze(int N) {
        solution = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                solution[i][j] = 0;
            }
        }
    }
  
    public void solveMaze(int[][] maze, int N) {
        if (findPath(maze, 0, 0, N, "down")) {
            print(solution, N);
        }else{
            System.out.println("NO PATH FOUND");
        }
          
    }
  
    public boolean findPath(int[][] maze, int x, int y, int N, String direction) {
 
        if(x==N-1 && y==N-1){
            solution[x][y] = 1;
            return true;
        }
        if (isSafeToGo(maze, x, y, N)) {
            solution[x][y] = 1;        
 
            if(direction!="up" && findPath(maze, x+1, y, N, "down")){
                return true;
            }
            if(direction!="left" && findPath(maze, x, y+1, N,"right")){
                return true;
            }
            if(direction!="down" && findPath(maze, x-1, y, N, "up")){
                return true;
            }
            if(direction!="right" &&  findPath(maze, x, y-1, N, "left")){
                return true;
            }
 
            solution[x][y] = 0;
            return false;
        }
        return false;
    }
  
 
    public boolean isSafeToGo(int[][] maze, int x, int y, int N) {
        if (x >= 0 && y >= 0 && x < N  && y < N && maze[x][y] != 0) {
            return true;
        }
        return false;
    }
    public void print(int [][] solution, int N){
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(" " + solution[i][j]);
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int N = 5;
         
        int[][] maze = { { 1, 0, 1, 1,1 },
                { 1, 1, 1, 0,1 },
                { 0, 0,0, 1, 1 },
                { 0, 0, 0, 1,0 },
                { 0, 0,0, 1, 1 } };
         
        System.out.println("Arrays for Maze1 : "+ Arrays.deepToString(maze));
         
        RatinMaze r = new RatinMaze(N);
        r.solveMaze(maze, N);
         
         
         int[][] maze2 = { { 1, 0, 1, 1,1 },
                { 1, 1, 1, 0,1 },
                { 0, 0,0, 1, 1 },
                { 0, 0, 0, 1,0 },
                { 0, 0,0, 0, 0 } };
          
         System.out.println("Arrays for Maze2 : "+ Arrays.deepToString(maze2));
          
         r.solveMaze(maze2, N);
          
         
         
    }
  
}

Output

Arrays for Maze1 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1]]
 1 0 1 1 1
 1 1 1 0 1
 0 0 0 1 1
 0 0 0 1 0
 0 0 0 1 1
Arrays for Maze2 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
NO PATH FOUND

Algorithm Explanation

Initialize the solution matrix as 1.
Move forward in the horizontal direction and recursively check if this move leads to a solution.
If the move chosen in the above step doesn’t lead to a solution, then move down and check if this move leads to a solution.
If none of the above solutions work then unmark this cell as 0 backtrack and return false.

Reference

  1. http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/
  2. https://www.cs.bu.edu/teaching/alg/maze
  3. https://en.wikipedia.org/?title=Maze

Write A Comment