How does this maze algorithm return the shortest path correctly?

Question

I came across this maze solver algorithm:

public class Maze {

    public static void main(String[] args) {
        char[][] maze = {
                {'.', '.', '.', '0', '0', '0', '0', '0', '0', '0'},
                {'0', '0', '.', '.', '.', '0', '.', '.', '.', '0'},
                {'0', '0', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '.', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '0', '0', '0', '.', '.', '.', '0', '.', '0'},
                {'.', '.', '.', '.', '0', '0', '0', '.', '.', '0'},
                {'.', '0', '0', '.', '.', '.', '0', '.', '.', '0'},
                {'.', '.', '.', '0', '0', '.', '0', '0', '.', '.'},
                {'0', '0', '.', '0', '0', '.', '.', '.', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '.', '.', '.'},
        };

        print(maze);

        if(traverse(maze, 0, 0)) {
            System.out.println("SOLVED maze");
        } else {
            System.out.println("could NOT SOLVE maze");
        }

        print(maze);
    }

    private static void print(char[][] maze) {
        System.out.println("-----------------------");
        for(int x = 0; x < 10; x++) {
            System.out.print("| ");
            for(int y = 0; y < 10; y++) {
                System.out.print(maze[x][y] + " ");
            }
            System.out.println("|");
        }
        System.out.println("-----------------------");
    }

    public static boolean isValidSpot(char[][] maze, int r, int c) {
        if(r >= 0 && r < 10 && c >= 0 && c < 10) {
            return maze[r][c] == '.';
        }
        return false;
    }

    public static boolean traverse(char[][] maze, int r, int c) {
        if(isValidSpot(maze, r, c)) {
            //it is a valid spot
            if(r == 9 && c == 9) {
                return true;
            }

            maze[r][c] = '*';

            //up
            boolean returnValue = traverse(maze, r - 1, c);


            //right
            if(!returnValue) {
                returnValue = traverse(maze, r, c + 1);
            }

            //down
            if(!returnValue) {
                returnValue = traverse(maze, r + 1, c);
            }

            //left
            if(!returnValue) {
                returnValue = traverse(maze, r, c - 1);
            }

            if(returnValue) {
                System.out.println(r + ", " + c);
                maze[r][c] = ' ';
            }
            return returnValue;
        }

        return false;
    }
}

but I can't work out the recursion in my mind. Even if the algorithm hits dead ends while searching for the exit spot and it marks the paths it passed through as invalid to pass through, it somehow returns to the last checkpoint, all while not printing the dead end paths. Which is the part that baffles me the most. How are dead end paths not printed in this algorithm?

I tried printing the maze at every step but still couldn't work out how invalid paths are not printed.

Answer 1

The function implements Depth First Search, also knows as DFS to find the path. You can read more on DFS and BFS here. What happens is basically as follow:

1. Checking if a current coordinate is the end coordinate, if it is returns True

2. Else, check if you can reach the end by advancing up

   2.1 if you can reach the end by advancing up, print this coordinate and return True

3. Else, check if you can reach the end by advancing right

   3.1 if you can reach the end by advancing up, print this coordinate and return True

4. Else, check if you can reach the end by advancing down

   4.1 if you can reach the end by advancing up, print this coordinate and return True

5. Else, check if you can reach the end by advancing left

   5.1 if you can reach the end by advancing up, print this coordinate and return True

6. Else, return False, meaning that from this coordinate you can not reach the end.

Instead of keeping a list of states to be visited, the information is being stored in the recursion.

A similar problem with DFS search of a path in a maze can be found here, implemented in Python and might be easier to understand the concept since it is not implemented with recursion but with a list.

Please note that the algorithm that is written does not find the shortest path, but it finds a path. To find the shortest path, you should use BFS since it covers all the paths with x steps before checking paths with x+1 steps.