Problem about maze resolution with backtracking java

Question

I'm trying to make an application which should resolve a maze, and I'm trying to make it with backtracking tecnique.

I have develop a code, and works for some easy scenarios but fails, in at least, one more complex.

Before I expose the code and the concrete problem I want to explain how it works.

ABOUT THE CODE

So I have two methods initializeMaze1 and initializedMaze2 which simply loads some presets scenarios (start point, some walls, and the end point).

I have no problems with the first one, but that changes with the second one.

Thouse methods give me a matrix of integers, whichs represents the entities (walls, start point...).

I have also a print method for depuration.

And finally the maze method which is the backtracking code. The parameters are:

1. The maze generated(which is done by the methods I talked about previously).
2. The position of the "player" in the rows of the maze.
3. The position of the "player" in the columns of the maze.
4. The solution. This is an other matrix which is going to give the path of the player, so I will mark the movements in there, and I will have the original maze untoched.

Now I'm going to talk deeper about the backtraking code.

BACKTRACKING CODE

So this method is a for loop which try some attemps (the attemps are possible moves of the player) so we try everyone until we obtain a valid movement or go back because there is no possible valid movement.

I have an isFactible method which analyzes the movement and says if it's ok or is not (if crashes with a wall or if goes out of the limits).

If is not factible, then tries with other movement (increases the iteration variable of the for loop).

If is not factible and we finish the loop, dismarks the actual position and return a false value (so the other context will knows about it).

If is factible, we will mark the new position and we need to diference between two posibilities:

• The position which we are going to move, is the end (the objetive or the exit), so we have success.
• The position which we are going to move, is not the end, so we call recursively again which the new position that we already moved.

Now I'm going to talk about the problems I found.

THE PROBLEMS

When I load the second maze, we have this scenario:

S: Start. E: Empty. W: Wall. F: Finish.

---

|S|E|W|W|

|E|E|E|E| Here is the problem

|E|E|W|W|

|W|E|E|F|

---

So the code, tries to move first to right, if not, tries down, if not tries left, and if not, tries up. We have that presets movement.

So move right, ok. Then tries to move right again, but there is a wall. So goes down, ok. Then, moves right until the last column. Tries to move right, he can't because goes out. Tries to move down, he can't, there is a wall. Tries to move left, he can, so moves there. And I have this infinite loop.

The first thing I thought is, ok, just add more restrictions, and avoid that he can move where he already has gone.

But I don't think it is a good solution.

Do you know how to resolve this? And maybe, if I made some mistakes in the code, or if the strategy I have chosen for resolve the problem is not good, I will appreciate your comments.

Thanks you kindly.

THE CODE

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

public class maze {

private static final int START = 1;
private static final int END = 2;
private static final int WALL = 3;
private static final int EMPTY = 0;
private static final int MOVE_RIGHT = 5;
private static final int MOVE_DOWN = 6;
private static final int MOVE_LEFT = 7;
private static final int MOVE_UP = 8;

public static void main(String[] args)
{
    int[][] solution = {{1,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
    showInitializationMessage();
    print(solution);
    if(maze(initializeMaze2(),0, 0, solution))
    {
        print(solution);
    }
    else
    {
        System.out.println("There is no solution");
    }
}

private static void showInitializationMessage()
{
    System.out.println("MAZE APPLICATION");
    System.out.println("_________________");
    System.out.println();
    System.out.println();
}

private static void print(int[][] solution)
{
    for(int i=0; i<solution.length;i++)
    {
        for(int j=0;j<solution.length;j++)
        {
            System.out.print(solution[i][j]);
        }
        System.out.println();
    }
    System.out.println();
    System.out.println("____________________");
    System.out.println();
}

private static int[][] initializeMaze1()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=WALL;
    maze[2][1]=EMPTY;
    maze[3][1]=WALL;

    //Setting column 2
    maze[0][2]=EMPTY;
    maze[1][2]=WALL;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=EMPTY;
    maze[1][3]=EMPTY;
    maze[2][3]=EMPTY;
    maze[3][3]=END;

    return maze;


}

private static int[][] initializeMaze2()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=EMPTY;
    maze[2][1]=EMPTY;
    maze[3][1]=EMPTY;

    //Setting column 2
    maze[0][2]=WALL;
    maze[1][2]=EMPTY;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=WALL;
    maze[1][3]=EMPTY;
    maze[2][3]=WALL;
    maze[3][3]=END;

    return maze;


}

private static boolean checkNotOutOfBounds(int[][] maze,int stepX, int stepY, int movement )
{
    if(movement==MOVE_RIGHT)
    {
        if(stepY+1>maze.length-1)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(stepX+1>maze[0].length)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(stepY-1<0)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(stepX-1<0)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkNotCollideWithObstacle(int[][] maze, int stepX, int stepY , int movement)
{
    if(movement==MOVE_RIGHT)
    {
        if(maze[stepX][stepY+1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(maze[stepX+1][stepY]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(maze[stepX][stepY-1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(maze[stepX-1][stepY]==WALL)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement)
{
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) && checkNotCollideWithObstacle(maze, stepX, stepY, movement))
    {
        return true;
    }
    return false;
}

private static boolean isFactible(int[][] maze,int stepX, int stepY, int[][] solution, int attemp)
{
    if(attemp==0)
    {
        //MOVE RIGHT
        return checkValidMovement(maze, stepX, stepY, MOVE_RIGHT);
    }
    else if(attemp==1)
    {
        //MOVE DOWN
        return checkValidMovement(maze, stepX, stepY, MOVE_DOWN);
    }
    else if(attemp==2)
    {
        //MOVE LEFT
        return checkValidMovement(maze, stepX, stepY, MOVE_LEFT);
    }
    else if(attemp==3)
    {
        //MOVE UP
        return checkValidMovement(maze, stepX, stepY, MOVE_UP);
    }
    return false;
}

private static boolean maze(int[][] maze,int stepX, int stepY, int[][] solution)
{

    boolean success =false;
    for(int attempt=0; attempt<4 && !success; attempt++)
    {
        //solution[stepX][stepY]=attempt???
        if(isFactible(maze,stepX, stepY, solution,attempt))
        {
            mark(solution,stepX, stepY,attempt);
            print(solution);
            int updatedStepX = updateStepX(stepX, stepY, maze, attempt);
            int updatedStepY = updateStepY(stepX, stepY, maze, attempt);

            if(maze[updatedStepX][updatedStepY]==END)
            {
                success=true;
            }
            else
            {
                success = maze(maze, updatedStepX, updatedStepY, solution);
            }
        }

    }
    if(!success)
    {
        solution[stepX][stepY]=0;
        print(solution);



    }
    return success;
}

private static void mark(int[][] solution, int stepX, int stepY, int attempt)
{
    if(attempt==0)
    {
        solution[stepX][stepY+1]=1;
    }
    else if(attempt==1)
    {
        solution[stepX+1][stepY]=1;
    }
    else if(attempt==2)
    {
        solution[stepX][stepY-1]=1;
    }
    else if(attempt==3)
    {
        solution[stepX-1][stepY]=1;
    }
}

private static int updateStepX(int oldStepX, int oldStepY, int[][] maze, int attemp)
{
    int updatedStepX=0;
    if(attemp==1)
    {
        updatedStepX=oldStepX+1;
    }
    else if(attemp==3)
    {
        updatedStepX=oldStepX-1;
    }
    else
    {
        updatedStepX=oldStepX;
    }

    return updatedStepX;
}

private static int updateStepY(int oldStepX, int oldStepY, int[][] maze, int attempt)
{
    int updatedStepY=0;

    if(attempt==0)
    {
        updatedStepY=oldStepY+1;
    }
    else if(attempt==2)
    {
        updatedStepY=oldStepY-1;
    }
    else
    {
        updatedStepY=oldStepY;
    }

    return updatedStepY;
}

}

Answer 1

As DrPhill said, you have to keep track where you've been. You're already doing that in function mark but you're not using that information in checkValidMovement function.

You should change that function to look like something like this:

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement, int[][] solution)
  {
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) 
        && checkNotCollideWithObstacle(maze, stepX, stepY, movement)
        && isNotYetVisited(maze, stepX, stepY, movement, solution))
    {
      return true;
    }
    return false;
  }   

where isNotYetVisited function returns false if the solution at next step is not equal 1.

Hope this helps.

Answer 2

I think that easiest way to do it is just remember coordinates of your last presence. If there are no valid moves other than going back, go back and mark the spot you were on as wall. Finally you will get to [F].

Answer 3

Much the same as you would (like to think you) solve a real maze.

For each location keep a record of which direction you arrived from and which (valid) directions you have left in (before you leave, I think).

When you return to a location (revisit should be allowed) treat an already tried direction the same way as a wall - ie it is invalid.

When you have no more valid directions return the way you came.

So the only difference from your code is remembering 'tried and failed' directions for each location. This should be enough to prevent recursion.