Find the a path in a grid from top left to bottom right using recursion

Question

I'm trying to move from the upper left corner to the bottom right corner of a grid using recursion. However, at each point in time, I can only move up, down, left, or right exactly the number of squares given by the number I'm standing on.

For example, if you were standing on a 3, I could move exactly three squares left, three squares right, three squares up, or three squares down. I can't move off the board. If a path is found the grid is displayed with particular entries indicating the move made e.g 3L (3 squares to the left) or 3R (# squares to the right). The variable length is the total path length

Here's my attempt at constructing the method. It returns a length, but the entries displayed in the grid don't give a sensible direction. Can someone help ?

public class Grid{
String [][] grid;
int n;

public void findPath()
    {


        int[][] visited = new int[n][n];

        if(FindPathHelper(0,0,visited, Clone(),0))
            System.out.println("Path was found!!!");
        else
            System.out.println("Path was not found");
    }


public boolean FindPathHelper(int x, int y, int[][] visited, Grid box, int length) {
        int n = box.grid.length; // Assuming n is the size of the grid
        if (x == n - 1 && y == n - 1) {
            box.Display(box.grid);
            System.out.println("Length is " + length);
            return true;
        }

        if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] == 1)
            return false;

        visited[x][y] = 1;

        int move = Integer.valueOf(grid[x][y]);


            box.grid[x][y] = move + "R";
            if (FindPathHelper(x + move, y, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "L";
            if (FindPathHelper(x - move, y, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "D";
            if (FindPathHelper(x, y - move, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "U";
            if (FindPathHelper(x, y + move, visited, box, length + move))
                return true;


        box.grid[x][y] = grid[x][y];
        visited[x][y] = 0; // Reset the visited flag if no path was found
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
  TestCases();


    }

    public static void TestCases(){
        System.out.println("Test Grid :");
        Grid testG = new Grid(5);
        testG.grid = new String[][]{{"1","2","5","4","3"},{"2","3","1","3", "1"},{"3","3","2","1","1"},
                {"5","2","2","4","2"},{"5","2","1","1","1"}};
        testG.Display(testG.grid);
        System.out.println();
        testG.findPath();
    }

This is the expected output from the test Case

Answer 1

the entries displayed in the grid don't give a sensible direction

This is because you have not implemented the directions correctly. First, as you use x as the first dimension (like in grid[x][y]), x represents a row, not a column, so in case of "R" your recursive call should not pass x + move, y as coordinates, but x, y + move. Secondly, "down" in your matrix means adding to the row number. So the sign of what you add should be opposite for the last two recursive calls. The correction would be:

        box.grid[x][y] = move + "R";
        if (FindPathHelper(x, y + move, visited, box, length + move))
            return true;

        box.grid[x][y] = move + "L";
        if (FindPathHelper(x, y - move, visited, box, length + move))
            return true;

        box.grid[x][y] = move + "D";
        if (FindPathHelper(x + move, y, visited, box, length + move))
            return true;

        box.grid[x][y] = move + "U";
        if (FindPathHelper(x - move, y, visited, box, length + move))
            return true;

Now, your code will display something like:

1R   2R   5    4D   3    
2    3    1    3    1    
3    3    2    1    1    
5    2    2    4    2    
5    2    1    1R   1    
Length is 8
Path was found!!!  

It is a quite different (and shorter) path than the one you presented as the expected output. Maybe there are some extra constraints you haven't mentioned, nor implemented.

Shortest path?

Note that your algorithm does not guarantee that the shortest path is found. It does not compare lengths of paths to check this. It contents itself with the very first path it finds, and immediately exits the search without looking for improvements.

So if it is intended to find a shortest path, then instead of those return true; in FindPathHelper, you'll have to keep going, and keep track of the shortest path found. For that you'll need an additional variable that represents the best solution so far. That could for instance be a clone of the Grid, or a string with the sequence of directions taken.

The downside of DFS is that you have to go through all possibilities. It would be better if you would implement a "best search" algorithm, like Dijkstra's algorithm or an A* algorithm. These algorithms extend multiple paths in parallel, always choosing the most promising first. If implemented well, the first path found will also be the shortest one.