In this post I would be discussing a method to solve mazes like the one shown in the adjoining diagram. The maze would be represented or modelled by using a double dimension array, where a space would represent an open path, a wall or a blockage would be represented by a hash (#) character and the character ‘F’ would mark the final destination. The starting point would be specified at the time of the function invocation.

Please note that in this post, we are interested in determining whether or not there exist a path between the starting point and the final point and not determining the shortest path.

From programming perspective, we have to develop a systematic approach to explore each path until a solution is found. It may be possible that some paths leads to a dead ends and in these cases we would be required to backtrack. This approach is known as ‘backtracking algorithm’.

We will use a recursive function to attempt to move in the top, bottom, right and left direction till we reach the destination or all the possible paths are exhausted. We would be placing the character ‘X’ to mark the path we are attempting to traverse which would be again replaced with a space in case we have to backtrack the maze.

The Java program to solve the maze i.e. detect whether a path exists between the source and the destination is as follows:

In this post I would be discussing a method to solve mazes like the one shown in the adjoining diagram. The mazed would be represented or modelled by using a double dimension array, where a space would represent an open path, a wall or a blockage would be represented by a hash (#) character and the character ‘F’ would mark the final destination. The starting point would be specified at the time of the function invocation.

Please note that in this post, we are interested in determining whether or not there exist a path between the starting point and the final point and not determining the shortest path.

From programming perspective, we have to develop a systematic approach to explore each path until a solution is found. It may be possible that some paths leads to a dead ends and in these cases we would be required to backtrack. This approach is known as ‘backtracking algorithm’.

We will use a recursive function to attempt to move in the top, bottom, right and left direction till we reach the destination or all the possible paths are exhausted. We would be placing the character ‘X’ to mark the path we are attempting to traverse which would be again replaced with a space in case we have to backtrack the maze.

The Java program to solve the maze i.e. detect whether a path exists between the source and the destination is as follows:

class Maze{
    char maze[][];
    public Maze( char maze[][] ){
        this.maze = maze;
    }

    public boolean findPath( int x, int y ){
        boolean found;
        if( maze[ x ][ y ] == 'F' ) 
            return true;
        if( maze[ x ][ y ] == '#' || maze[ x ][ y ] == 'X' ) 
            return false;
        maze[ x ][ y ] = 'X';
        found = false;
        for( int direction = 1; !found && direction <= 5 ; direction++ ){
            if( direction == 1 && (y-1) >= 0){
                found = findPath( x, y-1 ); // up
            }else if( direction == 2 && (x+1) < maze.length ){
                found = findPath( x+1, y ); // down
            }else if( direction == 3 && (y+1) < maze[0].length ){
                 found = findPath( x, y+1); //right
            }else if( direction == 4 && (x-1) >= 0 ){
                found = findPath( x-1, y ); // left
            }else if( direction == 5 ){
                found = false;
            }
        }
        if( !found ) maze[ x ][ y ] = ' '; // retreat
        return found;
    }

    public static void main( String args[] ){
        /*
        Maze is represented by a double dimension char array
        where,
        F is the destination cell,
        # is the blocked cell,
         is an open cell and 
        starting position (x,y) is specified whn invoking
        the function findPath
         */
        char m[][]= {   
                { '#', '#', '#', '#', '#', ' ', ' ', ' ', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', 'F', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', ' ', ' ', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', '#', '#', '#', '#', ' ', ' ' },
                { ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' }
            };
        Maze objMaze = new Maze( m );
        System.out.println( objMaze.findPath(1,1) );
    }
}

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement. Please note that the array maze is stands modified after the return from the function findPath( ) , meaning that one shouldn’t invoke the function findPath( ) again without removing the character X which is inserted while the findPath() function executes.