En mi solucion, al final esta el enlace al codigo fuente, pero pues lo pongo aqui tambien:
http://stuff.otaku-anime.com/Maze.class.php?source
Yo a falta de tiempo (y ganas xD) no me la quize complicar mucho sacando el camino mas corto, simplemente puse al raton a que recorriera el laberinto buscando el queso.
En si, la parte importante de mi clase seria el metodo solveMaze(), ya que este es el que se encarga de decidir (aleatoriamente) hacia que direccion moverse (buscando antes en que direcciones puede hacerlo) y volver a llamar la funcion hasta que se encuentre el queso.
Como se ve, el array original de laberinto esta modificado para que ocupe menos espacio, y no se si esto afecte el rendimiento (no deberia, creo yo), pero de ser asi entonces en cuanto pueda lo cambiaré por el arreglo original.
Al final quede contento con la solucion, ya que cumple su cometido y creo que es bastante flexible si se quisiera usar otro laberinto.
He estado viendo por encima las demas soluciones, y me parecen bastante ingeniosas, pero no las he visto tanto como para poder hacer un mejor comentario xD.. igual tenemos el transcurso de la semana para eso :3