public class MazeSolver {
    public static String findPath(Maze maze) {
        //Keep track of locations visited, defaults to all false values
        boolean[][] visited = new boolean[maze.getNumRows()][maze.getNumCols()];

        //This stack should contain a list of adjacent locations to get from entry to exit
        Stack<MazeLocation> solution = new StackRefBased<MazeLocation>();
        solution.push(maze.getEntry());
        String result = "";

        try {
            //Keep looking for a path to the exit until we reach the exit, or are out of options
            while (!solution.isEmpty() && !solution.peek().equals(maze.getExit())) {
                MazeLocation current = solution.peek();
                visited[current.getRow()][current.getCol()] = true;

                //Attempt to move right, then down, then left, then up, but only if it isn't visited yet
                if (!maze.isWall(current.getRow(), current.getCol() + 1) && !visited[current.getRow()][current.getCol() + 1]) {
                    //Move right
                    solution.push(new MazeLocation(current.getRow(), current.getCol() + 1));
                } else if (!maze.isWall(current.getRow() + 1, current.getCol()) && !visited[current.getRow() + 1][current.getCol()]) {
                    //Move down
                    solution.push(new MazeLocation(current.getRow() + 1, current.getCol()));
                } else if (!maze.isWall(current.getRow(), current.getCol() - 1) && !visited[current.getRow()][current.getCol() - 1]) {
                    //Move left
                    solution.push(new MazeLocation(current.getRow(), current.getCol() - 1));
                } else if (!maze.isWall(current.getRow() - 1, current.getCol()) && !visited[current.getRow() - 1][current.getCol()]) {
                    //Move up
                    solution.push(new MazeLocation(current.getRow() - 1, current.getCol()));
                } else {
                    //No new locations to move to, so backtrack
                    solution.pop();
                }
            }

            //The solution stack now contains a solution, or it is empty and the maze is not solvable.
            while (!solution.isEmpty()) {
                result = solution.pop() + result;
                if (!solution.isEmpty()) {
                    result = " " + result;
                }
            }

        } catch (StackEmptyException e) {
            System.out.println(e);
        }

        return result;
    }
}