Interview Question: The Mouse

I have a favorite interview question that I've been using over the last year.  It's time to get a new one, so I thought I'd share it with you all.  If you are not a Microsoft employee you might not be familiar with the interview process, but most technical positions involve a series of separate interviews where each interviewer will ask you to solve at least one problem relevant to your skill set. 

Of course, since I'm a developer, I ask people programming questions.  Finding an applicable solution to this problem should not be too difficult to most of you code slingers out there, but give it a try anyway since its fun.

The Setup

You are being asked to write the algorithm/software for a robotic mouse that needs to navigate a maze in order to find some cheese.  There are computing resources available, as wells as a modern programming language to develop your solution.   I'll describe the problem using C# but you may choose any common programming language.  The maze exists as a regular grid of squarish cells, potentially bordered on each side by a wall that prevents movement in that direction.  In one of these cells is the cheese, and in another is the mouse.  Neither location is known at the start of the search.

The interface you have by which to control the mouse is rather limited.   It has one function that moves the mouse in a cardinal direction, returning true/false depending on whether the move was successful or not, and another function that returns true if the cheese is actually in the mouse's current cell.

public interface IMouse {   bool Move(Direction d);   bool IsCheeseHere();}

public enum Direction {  North,  East,  South,  West}

Things to note:   The mouse is intended to be a physical mouse that must be moved via this interface.  The software is required to move the mouse to the cheese and then halt.  You may ignore the physical uncertainties of actual movement and assume that each successful move moves the mouse into the center of the adjacent cell, and each unsuccessful moves leave the mouse in its position.  You may also assume the maze to be limited to some reasonable size, at most 100x100 cells, and it is actually possible for the  mouse to reach the cheese.

Have fun an send me your solutions via the 'Contact Me' feature.   I'll post the best solutions next week.   You may also ask me questions using the comments below.

Matt