Robot Maze interview question and solution

Here's my solutions to a popular interview question.  You've given an interface with three methods.

• public boolean isAtEnd()
• public boolean moveForward()
• public void rotateRight()

Write an algorythem that can navigate a robot to the end of the maze.  The maze looks something like this...

    END
     X
     X
     X
XXXXXX
X
X
START

It's a pretty good question for a mid level Software Engineer.  Solving iterativly is pretty straight forward with one minor catch.  Unless you're keeping track of the number of turns the robot is taking you'll end up coming back from where you came from on the last turn.  Here's an examle of that solution.

    private void solveIteratively() {
        RobotMaze robotMaze = new RobotMaze();

        int turnCounter = 0;

        while (!robotMaze.isAtEnd()) {
            if (!robotMaze.moveForward()) {
                robotMaze.rotateRight();
                turnCounter++;
                if (turnCounter == 2) {
                    robotMaze.rotateRight();
                    turnCounter++;
                }
            }
            else {
                turnCounter = 0;
            }
        }

        System.out.println("We made it to the end iteratively!!!");
    }

When answering this question I think it's important to remeber to take a step back and run the solution through your head before jumping into code.  Something I'm not very good at.  ;)   And that being said here's the recursive solution.  

    private void solveRecursively(RobotMaze robotMaze, int turnCounter) {
        if ( robotMaze.isAtEnd()) {
            System.out.println("We made it to the end recursively!!!");
            return;
        }

        if (!robotMaze.moveForward()) {
            robotMaze.rotateRight();
            turnCounter++;
            if (turnCounter == 2 ) {
                robotMaze.rotateRight();
                turnCounter++;
            }
        }
        else {
            turnCounter = 0;
        }

        solveRecursively(robotMaze, turnCounter);
    }

You can find a full working example (including the implementation of the interface) on my github.  

• Interface
• Implementation
• Solution