Backtracking Algorithm: Basics

Introduction

Backtracking is a concept in which first we select one path and try to find the answer, if we don't reach the answer come back and try another path. Let's try to understand the with a simple example.

There is an actor how forgot his phone in any of these houses (A, B, C) Now he has to find his phone, so he starts with house A and checks if his phone is available. He didn’t find his phone in house A, so he backtrack(come back where he started). Now he goes to house B search for his phone here he found his phone came back and say he found his phone. He didn’t go to house C.

Now in the case where the actor has to find all the possible paths from his house to the Filming location. He has to travel all the paths from his house one by one to the Filming location. If he found any path which travels to the location he registers/remember came back chose next path and so on.. and at the end he finds all the possible path which reaches to the Filming location from his house.

Wikipedia definition:- Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

Problem: Rat In A Maze

You are given a N*N maze with a rat placed at maze[0][0]. Find whether any path exist that a rat can follow to reach its destination i.e. maze[N-1][N-1]. A rat can move in any direc­tion ( left, right, up and down). so we have to find a path to reach the end from start. In the Question, 2d array is given in which 1 means we can travel through this cell and 0(Zero) means it is blocked. For every block, the mouse can move in Up, Down, Left, Right.

Solution:

So for this, we are given N*N Matrix So we create a new 2d Array to keep track of whether we travel the path or not.

So we create a function with a parameter of the maze(2d array of the path already given), row(to keep track of rows), column(to keep track of columns), and an array (new array to keep track of traveled path).

So we check, how many ways we are not allowed to move to the cell?

1. if row<0
2. if row >= maze length
3. col<0
4. col >= maze.length
5. maze[row][col] == 0
6. arr[row][col] == 1

if any of the options ( 1to 6) is true we simply return.

if not in the options(1 to 6), then that is a valid cell and we can move to the cell/block.

so we make array cells as traveled.(arr[row][col] = 1).

Now check whether we reach the end or not if we reach the end we print the path of the array.

Now Important part Recursion:

from each block we have to move in four directions Up, Left, Down, Right.

1. to move Up — (row-1, column)
2. to move Left — (row, column+1)
3. to move Down — (row+1, column)
4. to move Right — (row, column-1)

so we call recursion for all four directions, if it is possible to move in the called recursion we move to the next block/cell and call recursion on the next cell/block, at the time of returning(no path available coming back in recursion) then we move in the next direction. In this way, we check for all possible directions for each possible block/cell.

Java Code:

public static void improveRatInMaze(int [][]maze,int row,int col,int[][]arr){
    // we check, how many ways we are not allowed to move to the cell?
    if(row<0 || row>=maze.length || col<0 || col>=maze.length || maze[row][col]==0 || arr[row][col]==1){
        return;
    }
    // if not in any of the options(1 to 6), then that is a valid cell, and we can move to the cell/block.

    //so we make array cells as traveled.(arr[row][col] = 1).
    arr[row][col] = 1;
    // check whether we reach the end cell/block.
    if(row==maze.length-1 && col==maze.length-1){
        // if we reach end print all possible path.
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
        }
        System.out.println();
        //making the array cell not traveled.
        arr[row][col]=0;
        return;
    }
    // calling recursion on all four direction

    // UP
    improveRatInMaze(maze,row-1,col,arr);
    // Down
    improveRatInMaze(maze,row+1,col,arr);
    // Right
    improveRatInMaze(maze,row,col+1,arr);
    // Left
    improveRatInMaze(maze,row,col-1,arr);
    
    // if not reach the end cell/block for certain path
    // making the array cell not traveled.
    arr[row][col] = 0;
}

Thanks. Please comment and clap and follow.