1. Problem description

The problem is that we have to construct an algorithm that can find its way out of an NxN maze. We can represent this maze with an NxN matrix. The maze problem is a classic application of Depth First Search (DFS), where the objective is to find a path from a starting point to a destination in a maze. DFS explores the maze systematically by traversing as far as possible along one path before backtracking if a dead end is encountered.

• Input: A grid-like maze consisting of open paths (passable cells) and walls (impassable cells). The maze has a starting point and a goal point.
• Output: A path from the starting point to the goal (if one exists) or a statement that no path exists.

The maze can be represented as a 2D grid where:

• 0 represents a wall
• 1 represents an open path
• The start and goal points are defined by their grid coordinates.

There may be several algorithms for the problem:

• If we know the maze then we can use the Dijkstra’s algorithm and A* search.
• If we do not know the maze, we can use backtracking.

2. Algorithm

• Start from the initial position.
• Mark the current cell as visited.
• Explore all possible directions (up, down, left, right) from the current cell.
• If the goal is reached, return the path.
• If no more moves are possible, backtrack and try another direction.
• If all paths are explored and the goal is not found, conclude that no path exists.

Here is the sample maze:

[
[1,1,1,1,1,1],
[2,1,0,0,0,1],
[0,1,0,1,0,1],
[0,1,0,1,0,0],
[0,1,0,1,1,0],
[0,0,0,1,0,3],
]

So we have a map like this:

• integer 1 represents obstacles
• integer 2 is the starting point
• integer 0 represents the states we can consider

3. Implementation

MazeSolver.java

public class MazeSolver {
    private int startRow;
    private int startCol;
    private int[][] maze;
    private boolean[][] visited;

    public MazeSolver(int[][] maze, int startRow, int startCol){
        this.maze=maze;
        this.visited=new boolean[maze.length][maze.length];
        this.startRow=startRow;
        this.startCol=startCol;
    }
    private boolean isFeasible(int x, int y){
        // check the vertical dimension
        if(x<0 || x>maze.length-1){
            return false;
        }
        // check the horizantal dimension
        if(y<0 || y>maze.length-1){
            return false;
        }
        // when we have already considered that state
        if(visited[x][y])
            return false;
        //there is an obstacle
        if(maze[x][y]==1)
            return false;

        return true;

    }

    private boolean dfs(int x, int y){
        if(x==maze.length-1 && y==maze.length-1)
            return true;

        if(isFeasible(x,y)){
            visited[x][y] = true;

            // then we have to visit the next cells Up, Down, Left, Right

            //visit cells down
            if(dfs(x+1, y))
                return true;

            //visit cells up
            if(dfs(x-1,y))
                return true;

            //visit cells right
            if(dfs(x,y+1))
                return true;

            //visit cells left
            if(dfs(x, y-1))
                return true;

            //backtrack
            visited[x][y]=false;
            return false;
        }
        return false;
    }
    public void findWay(){
        if(dfs(startRow, startCol)){
            System.out.println("Path exists to the destination");
        } else {
            System.out.println("No path exists");
        }
    }
}

App.java

import java.util.List;
import java.util.ArrayList;

public class App {
    public static void main(String args[]){
        int[][] map={
                {1,1,1,1,1,1},
                {2,1,0,0,0,1},
                {0,1,0,1,0,1},
                {0,1,0,1,0,0},
                {0,1,0,1,1,1},
                {0,0,0,1,0,3},
        };

        MazeSolver mazeSolver = new MazeSolver(map, 1, 0);
        mazeSolver.findWay();
    }
}