Total ways to reach destination by snake using Backtracking In Java

In this Java tutorial, we are going to find all the possible paths for reaching the snake to the destination by using backtracking technique. Suppose we have a n*m cells path and snake starts from one end of the path and he has to reach the opposite last cell which is the destination for snake apart from this there is eagle also in the path, the value of that cell is -1 and snake can’t move to that cell.

Total ways to reach the destination by snake using Backtracking in Java

In this puzzle, snake is only allowed to move right and down.

What is Backtracking?

Backtracking is an algorithm technique which searches every possible combination to solve a computational problem.

There are three types of backtracking problem :-

1. Decision problem:- Here, we search for the feasible solution.
2. Optimization problem:- Here, we search for the best solution.
3. Enumeration problem:- Here, we find all feasible solution.

Step by Step Approach for the problem:-

1. If the initial cell is blocked, then there is no way to move anywhere so, return 0.
2. As snake can move either downward or right, so initialize the first row and first column as 1. If snake found eagle in the path means cell value – 1, then there is no way to go beyond that cell, so simply break the loop from there.
3. Now, calculate the all possible paths from a particular cell to reach the destination by using the Backtracking technique, by visiting the unvisited path and explore it.

Java Code to Calculate all possible paths for the snake

import java.util.Scanner;

class Codespeedy
{
    static int result ( int a[][] , int m , int n)
    {
        int i,j;
    
        
        if ( a[0][0]==-1 )
             return 0;
        
        for (i=1 ; i<m ; i++)
         {
             if(a[i][0]==0)
              a[i][0]=1;
              
              else 
                break;
         }
         
           for (j=1 ; j<n ; j++)
         {
             if(a[0][j]==0)
              a[0][j]=1;
              
              else 
                break;
         }
        
        for( i=1 ;i<m ;i++)
         {
             for( j=1;j<n;j++)
             {
                 if (a[i][j] == -1)
                   continue;
                   
                  if(a[i-1][j]>0)
                   a[i][j] = ( a[i][j] + a[i-1][j]);
                   
                   if(a[i][j-1]>0)
                   a[i][j] = ( a[i][j] + a[i][j-1]);
                 
                 
             }
         }
        
        return a[m-1][n-1];
    }
    
    public static void main ( String[] args)
     {
         Scanner scan = new Scanner(System.in);
         
         System.out.println("Enter no. of rows");
          int x = scan.nextInt();
          
         System.out.println("Enter no. of columns");
          int y = scan.nextInt();
         
         int a[][] = new int[x][y];
         
         for(int i=0; i<x; i++)
       {
           for(int j=0; j<y; j++)
           {
               int k=scan.nextInt();
               a[i][j] = k;
           }
       }
       
       System.out.println(result(a,x,y));
     }
}

INPUT

Enter no. of rows
4
Enter no. of columns
4
0 0 0 0
0 -1 0 0
-1 0 0 0
0 0 0 0

OUTPUT
4

Also read,

• Program to find all permutations of a string in Java
• Maximum Coin Spend Problem using Dynamic Programming in Java