How to backtrace in a maze...?

Question

So I'm writing a program to make a robot explore a maze to find a specified cavern. There are four types of Cells: Cavern, Start, Wall, and Passage. Robots can only move to a passage or a cavern. I implemented my method so that a robot can't move to a visited cell or go out of bounds. But once it moves to a cell where there isn't a valid adjacent cell, the program stops. So how do I make my robot backtrace to where there is a valid cell? I'm using a recursion for this. Below is my code. Any help will be great. Thank you!

public void explore (Cell cavern, Maze maze) throws InterruptedException {
    // for debugging
    System.out.println(row + " " + col);
    System.out.println(cavern.getRow() + " " + cavern.getCol());
    System.out.println(visited.toString());
     TimeUnit.MILLISECONDS.sleep(10); // delay program
    //base case
    if (row == cavern.getRow() && col == cavern.getCol()) {
        foundCavern = true;
        return;
    }
    else {
        // move right
        if ((col+1) < maze.getNumCols() && !visited.contains(maze.getCell(row, col+1)) && (maze.getCell(row, col+1).isPassage() || maze.getCell(row, col+1).isCavern())) {
            visited.add(maze.getCell(row, col+1));
            setRobotLocation(row,col+1);
            explore(cavern, maze);
        }
        // move down
        else if ((row+1) < maze.getNumRows() && !visited.contains(maze.getCell(row+1, col)) && (maze.getCell(row+1, col).isPassage() || maze.getCell(row+1, col).isCavern())) {
            visited.add(maze.getCell(row+1, col));
            setRobotLocation(row+1,col);
            explore(cavern, maze);
        }
        // move left
        else if ((col-1) >= 0 && !visited.contains(maze.getCell(row, col-1)) && (maze.getCell(row, col-1).isPassage() || maze.getCell(row, col-1).isCavern())) {
            visited.add(maze.getCell(row, col-1));
            setRobotLocation(row,col-1);
            explore(cavern, maze);
        }
        // move up
        else if ((row-1) >= 0 && !visited.contains(maze.getCell(row-1, col)) && (maze.getCell(row-1, col).isPassage() || maze.getCell(row-1, col).isCavern())) {
            visited.add(maze.getCell(row-1, col));
            setRobotLocation(row-1,col);
            explore(cavern, maze);
        }
        else {
            foundCavern = false;
            return;
        }
    }
}

Answer 1

I think you are in the right direction. What I think you should do is keep checking for all direction unless you found the cavern. Right now you are checking for only one direction in each iteration because of the else clause. So when the call to explore returns you can't keep checking a different direction and essentially you don't backtrack. If you make your explore function return a Boolean field indicating whether you reached the cavern changing your code like this may work:

// move right
if ... // your condition to check if moving right is possible and you didn't visit
// code to move right
found = explore()
//move down if didn't find cavern
if (!found) // and moving down is possible and didn't visit
// code to move down
found = explore()
// keep checking other directions