java:Maze Solver using Backtracking stuck in Loop

Question

i want to solve maze by backtracking,after a little googling! i see this algorithm: Recursion: Solving a Maze

here it is:

FIND-PATH(x, y)

1. if (x,y outside maze) return false

2. if (x,y is goal) return true

3. if (x,y not open) return false

4. mark x,y as part of solution path

5. if (FIND-PATH(North of x,y) == true) return true

6. if (FIND-PATH(East of x,y) == true) return true

7. if (FIND-PATH(South of x,y) == true) return true

8. if (FIND-PATH(West of x,y) == true) return true

9. unmark x,y as part of solution path

10. return false

i try to implement it correctly,as below:

public class main {

public static void main(String[] args) {
    // A as a Start and B is finish Line
    char maze[][] = { 
            { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
            { '#', 'A', ' ', ' ', '#', ' ', '#', ' ', ' ', '#' },
            { '#', ' ', ' ', ' ', '#', ' ', '#', ' ', '#', '#' },
            { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
            { '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
            { '#', '#', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
            { '#', ' ', ' ', ' ', ' ', '#', '#', '#', '#', '#' },
            { '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#', '#' },
            { '#', 'B', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#' },
            { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }

    };

    for (int i = 0; i < maze.length; i++) {
        System.out.println(maze[i]);
    }

    mazeTraversal(maze, 1, 1);
}

static boolean mazeTraversal(char m[][], int i, int j) {
    if (m[i][j] == '#')
        return false;
    if (m[i][j] == 'B')
        return true;
    // marking as a part of path
    m[i][j] = '*';
    //north
    if ((mazeTraversal(m, i , j - 1)) == true) {
        return true;
    }
    //east
    if ((mazeTraversal(m, i + 1 , j)) == true) {
        return true;
    }
    //south
    if ((mazeTraversal(m, i , j + 1)) == true) {
        return true;
    }
    //west
    if ((mazeTraversal(m, i - 1, j)) == true) {
        return true;
    }
        m[i][j] = ' ';
        return false;
}
}

here is the console error: (stack overflow)!

Exception in thread "main" java.lang.StackOverflowError
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)
    at main.mazeTraversal(main.java:43)
    at main.mazeTraversal(main.java:35)

also i've done a few times tracing and i see it stuck in a loop and it never go further... is that my code wrong or the algorithm is wrong?

Answer 1

An open square is a square that does not contain # or *, you're only checking for #.
The * check is required to not end up in infinite recursion (ie going back the same way you just came)

Changing your code to;

static boolean mazeTraversal(char m[][], int i, int j) {
    if (m[i][j] == '#')
        return false;
    if (m[i][j] == 'B')
        return true;
    if (m[i][j] == '*')    // <-- added check
        return false;
    // marking as a part of path
...

...and printing the result after running the solver gives;

##########
#A  # #  #
#   # # ##
#        #
#        #
###      #
#    #####
#     # ##
#B#      #
##########

##########
#*  # #  #
#*  # # ##
#*       #
#***     #
###*     #
#*** #####
#*    # ##
#B#      #
##########

...which looks like what you're trying to do.