Recursive backtracking returning updated value

Question

I'm creating a program designed to recursively navigate a maze. The code:

public static boolean traverse(int maze[][], coordinate start)
{
    //recursion: traverse(maze, updated coordinates)

    if(maze[start.y+1][start.x] == 2 || maze[start.y-1][start.x] == 2 || maze[start.y][start.x+1] == 2 || maze[start.y][start.x - 1] == 2)
    {
        display(maze);
        System.out.println("DONE");
        return true;
    }

    else 
    {
        if(north(maze, start) == true)
        {
            maze[start.y-1][start.x] = 4;
            display(maze);
            coordinate temp = start; 
            temp.y--;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;

            }
        }   

        if(west(maze, start) == true)
        {
            maze[start.y][start.x-1] = 4;
            display(maze);
            coordinate temp = start;
            temp.x--;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }


        if(south(maze, start) == true)
        {
            maze[start.y+1][start.x] = 4;
            display(maze);
            coordinate temp = start;
            temp.y++;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }

        if(east(maze, start) == true)
        {
            maze[start.y][start.x+1] = 4;
            display(maze);
            coordinate temp = start;
            temp.x++;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }   


    }

    return false;
}

However whenever I reach a dead end, it doesn't backtrack. When I debug, it shows that my start values are fixated on staying at my dead end space when the program returns from the recursion or "backtracks".

For example:

1 1 1 1 1 
1 4 4 4 1 
1 9 1 4 1 
1 1 1 4 1 
1 4 4 4 1 
1 4 1 0 1 
1 4 1 0 1 
1 1 1 2 1  

9 is my starting point. 2 is my exit. 4 is my path. 1 represents the walls. When I reach a dead end (in this case row 7, column 2). My position be would equal to that dead end space throughout the rest of the program. Why's that?

Answer 1

As you move up the stack, the values get updated and never "backtrack" since they dont retain their original values in each level, backtracking is basically walking a tree, if each node does not retain the original value when you update it at each level, every node will have the value of the leaf node , when the leaf node is met, nodes do not remember their original value. Instead you need to pass a new value as you traverse up the stack without updating for each stack to remember what they had when they were called by their parent.

Easiest way is to try,

 traverse(int maze[][], int x , int y)

and your subsequent call will look something like

 if(north(maze, x , y) == true)
    {
        maze[y-1][x] = 4;
        display(maze);

        //temp.y--;
        if (traverse(maze, x , y-1) == false)
        {
            maze[y][x] = 3;

        }
    }

or you could reset your value back after you return to the current stack,

I havent checked the rest of your code, but this is probably the reason for the code not to backtrack

Answer 2

You can shorten that alot. Try out his code.

public static boolean traverse(int[][] maze, int x, int y) {
    if(y >= maze.length || x >= maze[y].length) return false;
    int value = maze[y][x];
    if(value == 2) {
        display(maze);
        System.out.println("DONE");
        return true;
    } else if(value == 0 || value == 9) {
        maze[y][x] = 4;
        boolean success = false;
        loop:
        for(int dy = -1; dy <= 1; dy++) {
            for(int dx = -1; dx <= 1; dx++) {
                if(dx == 0 && dy == 0 ||
                   dx != 0 && dy != 0) continue;
                success |= traverse(maze, x + dx, y + dy);
                if(success) break loop;
            }
        }
        maze[y][x] = value;
        return success;
    }
    return false;
}

public static void main(String[] args) {
    int[][] maze = {{1, 1, 1, 1, 1}, 
                    {1, 0, 0, 0, 1},
                    {1, 9, 1, 0, 1},
                    {1, 1, 1, 0, 1},
                    {1, 0, 0, 0, 1},
                    {1, 0, 1, 0, 1},
                    {1, 0, 1, 0, 1},
                    {1, 1, 1, 2, 1}};
    int x = 0, y = 0;
    loop:
    for(y = 0; y < maze.length; y++) {
        for(x = 0; x < maze[y].length; x++) {
            if(maze[y][x] == 9) break loop;
        }
    }
    boolean success = traverse(maze, x, y);
    System.out.println();
    System.out.println(success);
    display(maze);
}