Hola,
el siguiente laberinto fue diseñado por Minotaur Designs y apareció en Scientific American en diciembre de 1986:
Se entra al laberinto por donde indica la flecha (R) y se quiere llegar a la meta (situada en el centro) en el mínimo número de pasos. En cada nodo se DEBE cambiar de color. Por ejemplo, si se entra en el nodo I por un camino de color azul hay que salir obligatoriamente por el rojo.
Como no es lo mismo entrar a un nodo por un color o por otro, considero que hay un total de 19 nodos en vez de los 8 que se ven a bote pronto (nodo R entrando por rojo, nodo R entrando por azul, nodo R entrando por amarillo, nodo A entrando por rojo, nodo A entrando por amarillo, etc).
He hecho la matriz de adyacencia del grafo (es dirigido y por tanto no simétrica). Las filas y columnas siguen el siguiente orden:
R,
R,
R,
A,
A,
T,
T,
T,
O,
O,
O,
M,
M,
N,
N,
I,
I,
U,
U
Perdonad que no copie la matriz en Latex, es 19x19 y perdería demasiado tiempo.
Queremos que el elemento \( M_{1,13}\neq{0} \), es decir, que se pueda ir de
R a
M. En la matriz \( M^1 \) este elemento es 0. Con Python he ido multiplicando la matriz por sí misma hasta que he llegado a \( M^7 \). En la matriz \( M^7 \), la posición \( M_{1,13} \) es 1. Por tanto el laberinto se puede solucionar en un mínimo de 7 pasos.
Mi pregunta es: ¿cómo sé matemáticamente cuál es el camino a seguir para resolver el laberinto? Conozco el mínimo número de pasos pero no el camino. Siendo un poco astutos nos damos cuenta que la editorial se llama Minotaur y en el laberinto aparecen exactamente esas mismas letras. Probando vemos que la solución al laberinto es R-U-A-T-O-N-I-M (el nombre al revés). ¿Pero como obtengo este camino sin tener que recurrir al prueba y error?
Saludos.
