Recursive Maze Solver method Issue

Question

Given a 2 dimensional char array filled with 0's and 1 where 0 represents a wall and 1 represents a valid path, I have developed a recursive method called findPath(int r, int c) to find the exit in the maze marked with an 'x'. The method takes in the current row and column of the maze and goes through N,E,S,W directions until it finds a valid path and marks that valid path with a '+'. Given an instance where all directions are found to be blocked by a wall, the method then is suppose to backtrack until this is not the case anymore, and then marking that path traveled with an 'F' to symbolize the bad path.

Right now I can't figure out why the findPath method doesn't seem to transverse through all the directions as my display method just shows the program starting from the coordinates I pass in and not moving anywhere from there, why could this be?

Here is my Driver class

public class MazeMain2
{   
    public static void main(String[]args)
    {

    char[][] mazeArr = {{'0','0','0','1','0','0','0','0','0','0','0','0','0','0','0'},
                {'0','0','0','1','0','0','0','0','1','0','0','0','0','1','0'},
                {'0','0','0','1','1','1','1','1','1','1','1','1','0','0','0'},
                {'0','0','0','1','0','0','0','0','0','0','0','1','0','0','0'},
                {'0','0','0','1','1','1','1','1','0','0','0','1','0','0','0'},
                {'0','0','0','0','0','0','0','1','0','0','0','1','0','0','0'},
                {'0','0','0','0','1','1','1','1','0','0','0','1','0','0','0'},
                {'0','0','0','0','1','0','0','1','0','0','0','1','0','1','0'},
                {'0','0','0','0','1','0','0','1','0','0','0','0','0','0','0'},
                {'0','0','0','0','1','0','0','0','0','0','0','0','0','0','0'},
                {'0','0','0','0','1','1','1','1','1','1','1','0','0','0','0'},
                {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'},
                {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'},
                {'0','0','0','0','0','1','0','0','0','0','1','1','1','1','0'},
                {'0','0','0','0','0','0','0','0','0','0','1','0','0','0','0'}};

    MazeSolver2 mazeS = new MazeSolver2(mazeArr);

    mazeS.markEntry();
    mazeS.markExit();

    mazeS.solve(0, mazeS.start);


    }
}

And here is my maze solver class with the findPath method

public class MazeSolver2
{
    int start;
    int exit;

    char[][] maze;

public MazeSolver2(char[][] currentMaze)
{
    maze = currentMaze;
}

//Finds where the first 1 is in the top row of the 
//maze (entrance)
public void markEntry()
{
    for(int x = 0; x < maze.length; x++)
    {
        if(maze[0][x] == '1')
        {
            maze[0][x] = 'E';
            start = x;
        }
    }
}

//Finds where the last 1 is in the bottom row of the 
//maze (exit)
public void markExit()
{
    for(int x = 0; x < maze.length; x++)
    {
        if(maze[maze.length - 1][x] == '1')
        {
            maze[maze.length - 1][x] = 'x';
            exit = x;
        }
    }
}

public void solve(int x, int y)
{
    if(findPath(x, y))
    {
        System.out.println(maze[x][y]);
    }
    else
        System.out.println("No solution");

}

public boolean findPath(int r, int c)
{   
    displayMaze(maze);

    //Found the exit
    if(maze[r][c] == 'x')
    {
        return true;
    }


    if(maze[r][c] == '0' || maze[r][c] == '+' || maze[r][c] == 'F')
    {
        return false;
    }

    maze[r][c] = '+';

    //If row is currently at zero then don't check north
    //direction because it will be outside of the maze
    if(r <= 0)
    {
        if(findPath(r, c++))
        {
            return true;
        }


        if(findPath(r++, c))
        {
            return true;
        }

        if(findPath(r, c--))
        {
            return true;
        }

    }

    else
    {
        //check N, E, S, W directions
        if(findPath(r--, c) || findPath(r, c++) ||
            findPath(r++, c) || findPath(r, c--))
        {
            return true;
        }
    }

    //Marking the bad path
    maze[r][c] = 'F';

    return false;

}

//Displays maze
public void displayMaze(char[][] maze)
{

        for(int row = 0; row < maze.length; row++)
        {
            for(int col = 0; col < maze.length; col++)
            {
                if(col == 14)
                {
                    System.out.print(maze[row][col]);
                    System.out.println();
                }
                else
                {
                    System.out.print(maze[row][col]);
                }
            }
        }   

    System.out.println();
    }
}

You are a victim of the [post increment operator](http://stackoverflow.com/questions/2371118/how-do-the-post-increment-i-and-pre-increment-i-operators-work-in-java). Always increment on a new line. — abhipil, Apr 16 '17 at 06:51
FYI - your code will throw an exception if your entry point is at (0, 0). Check out `if(findPath(r, c--))` — Tah, Apr 16 '17 at 06:52

score 2 · Accepted Answer · answered Apr 16 '17 at 09:20

Your algorithm has several flow in itself, which I don't feel right to point out. You can search for maze traverse problems, and get many good tutorials.

However, give attention to the method calls. Notice that if findPath(int r, int c) get called with findPath(5, 5) then a call to findPath(r, c++) passes the values findPath(5, 5) again, not with findPath(5, 6).

Because in that case findPath(r, c++) get called with current value of c and after that c++ gets executed.

Same goes for findPath(r, c--) findPath(r++ , c) etc, etc.

A good idea to understand the fact is to print the values int r, int c at the starting of method findPath(). Also play a little with post increments/decrements(x++/--x) and pre increments/decrements(++x/--x).

Hope it helps.

Recursive Maze Solver method Issue

1 Answers1