Pues este problema parece demasiado interesante como para no participar
Mi 'algoritmo de media hora' (porque en ese tiempo lo hice
) es bastante pobre, simplemente recorre el laberinto intentando no pasar más de una vez por la misma casilla (aunque no lo logro, ya que no supe cómo equilibrar el "no pases más de 1 vez" con el "si me estanco tengo que volver").
En definitiva, el ratón siempre encuentra el queso. Y al contrario del ratón de Caricatos, el mío no tiene visión de rayos X para ver todo el laberinto hasta encontrar el queso...
Estuve viendo problemas similares, un amigo me sugirió buscar
Backtracking... aún no sé si fue un algoritmo así el que usó caricatos, pero lo que sí se es que voy a leer esa página hasta entenderlo
http://www.tallerwebmaster.com/alvli.../laberinto.php
Saludos.