CODEWITHSUNDEEP
java
idan di
idan di

Reputation: 241

find it hard to get the idea of backtracking in my mind, can i get some help please?

my problem is. i wrote a code. i get as my output false instead of true. i tried every posibble solution of which i can think of. i need some help . i just finished recursion course. i finished the material. i wrote some programs using recursion, and i did it well. i have a problem with backtracking. for example, this one. i need to arrive the [n-1][n-1] position from the start[0][0] i cant use go through diagonals, only up ,down ,left ,right. the path needs to be in the pattern of - if the next index is largerby one then the index before him. i tried to write the code. it should return true but it returns false. also this picture s only example. it should be working on any n*n array the picture : !find a path from (0,0) until [n-1][n-1]

public class Backtrack
{

    public static boolean isPath(int [][] arr)
    {
       return isPath(arr ,0 ,0, 0 ,0 );
    }

    //checks that i'm not out of bounceof the array
    private static boolean isSafe(int[][] arr, int row, int col, int x,int y) {
       if(x >= 0 && x < arr[0].length && y >= 0 && y < arr.length && 
       row >= 0 && col >= 0 && row < arr.length && col < arr[0].length)
          return true;

     return false;
     }
    //checks the path
    private static boolean isPath (int [][] arr, int row, int col,int x,int y)
    {
      //if next index is not 1 larger then the previous one  @return false
       if (arr[row][x]!= arr[y][col] + 1)
          return false;  
       //if arrived to arr[n-1][n-1] position.then the path was found. @return       true goal achived
       if (row==arr.length-1 && col==arr.length-1)
          return true;
       if(isSafe(arr, row, col, x, y) == true) {

           if(isPath(arr,row, col, ++x, y) == true)
               return true;
           if(isPath(arr, row, col, x , ++y) == true)
               return true;

        return false; 
       }
    return false;
    }
}

Upvotes: 1

Views: 565

Answers (1)

Billy Hardy
Billy Hardy

Reputation: 33

Some initial problems I caught:

  • You are confusing your parameters. From the looks of it, you want arr[row][col] to reference the previous space and arr[x][y] to be the next space.
  • You check if the current square is correctly related to the previous one. In theory this works, but it fails right when you start out since you pass the same value for the current and previous (i.e. return isPath(arr ,0 ,0, 0 ,0 );).
  • You check if the current values are okay, when you should be checking if the new values are. if(isSafe(arr, row, col, x, y) == true) { should be if(isSafe(arr, row, col, x+1, y) == true) { and similar for the four other directions you can go.
  • You are incrementing x and y when you should be just adding 1. if(isPath(arr,row, col, x+1, y) == true). The way you have it, you will be going on diagonals.
  • You don't cover the up and left directions.

Hope this helps.

Upvotes: 1

Related Questions