Maze solver java

Question

I need to write a maze solving program for APCS that involves a text-based matrix of ones and zeros. I have to write code which finds a path, if there is one, from coordinate 0,0 to anywhere on the right side. Here is what I have so far

public class Maze {
    private int[][] maze;
    private int sizes = 0;
    private boolean[][] checked;

    public Maze(int size, String line) {
        checked = new boolean[size][size];
        sizes = size;
        out.println(sizes - 1);
        Scanner joe = new Scanner(line);
        maze = new int[size][size];
        for (int x = 0; x < size; x++) {
            for (int y = 0; y < size; y++) {
                maze[x][y] = joe.nextInt();
            }
        }
    }

    public boolean hasExitPath(int r, int c) {
        boolean solved = false;
        boolean wall = false;

        if (r == sizes - 1) {
            solved = true;
            return solved;
        }

        maze[r][c] = 2;
        if (maze[r + 1][c] == 1) {
            out.println("down");
            hasExitPath(r + 1, c);
        }else if (maze[r][c + 1] == 1) {
            out.println("left");
            hasExitPath(r, c + 1);
        }else if (maze[r - 1][c] == 1) {
            out.println("up");
            hasExitPath(r - 1, c);
        }else if (maze[r][c - 1] == 1) {
            out.println("right");
            hasExitPath(r, c - 1);
        }
        System.out.println(r + " " + c);
        return solved;
    }

    public String toString() {
        String output = "";
        for (int y = 0; y < sizes; y++) {
            for (int x = 0; x < sizes; x++) {
                output = output + maze[y][x];
            }
            output = output + "\n";
        }
        return output;
    }
}

Here is the main class

public class MazeRunner {
    public static void main(String args[]) throws IOException {
        Scanner mazeinfo = new Scanner(new File("maze.dat"));

        int size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        String b = mazeinfo.nextLine();
        Maze m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));

        size = mazeinfo.nextInt();
        mazeinfo.nextLine();
        b = mazeinfo.nextLine();
        m = new Maze(size, b);
        out.println(m);
        out.println(m.hasExitPath(0, 0));
    }
}

Here is an image of the mazes that need to be solved

https://drive.google.com/file/d/0BzE3Cu7SjRlNdzRHYjM4UzZkY00/view?usp=sharing

I added a bunch of debug code in the hasExitPath method to help me understand what was going on. Whenever I run the program, it just can't seem to trace the maze. What do I need to add to this program?

Answer 1

I'd advise against the recursive approach, if the maze gets big enough you could have a stack overflow problem. what i'd advise you to do is to operate based on a direction that you travel in and re-evaluate the direction based on whether you reach an intersection or a dead end. i can give you a link to some code which works on a maze problem but not using a 2d array.

Answer 2

calling hasExitPath(r , c) will always return false, unless r == size - 1 is true. Since you start at with r == 0, and size > 0 is true, the code will always result with false. Use

if(hasExitPath(r + 1, c))
     return true;

instead of simply calling hasExitPath(r + 1, c);, to solve this problem (same for all other recursive calls to hasExitPath(r , c)).