El algoritmo de Tarry o cómo salir de un laberinto a la primera

Esta situación se puede interpretar matemáticamente como un grafo en el que cada uno de los nodos representa uno de los barrios de Königsberg separados entre sí por el río, y los puentes se entienden como las aristas entre los nodos respectivos. El recorrido buscado no sería más que un camino que recorriera todos los nodos del grafo pasando una única vez por cada arista y volviendo al nodo inicial (circuito euleriano). Euler demostró que dicho recorrido existiría siempre y cuando el grado de cada nodo (esto es, el número de aristas incidentes al mismo) fuera par. Observando el grafo anterior que describe la situación de los puentes (los círculos son los nodos que indican las diferentes zonas, y las aristas representan los puentes), se observa que a todos los nodos llega un número impar de aristas. Por tanto, de acuerdo con el resultado anterior, es imposible realizar un circuito euleriano.

Si modificamos los supuestos iniciales del problema estableciendo que los puntos de partida y de fin fueran distintos, entonces habría que buscar un camino euleriano y las condiciones para su existencia son diferentes. Por otra parte, si lo que se buscara fuera una ruta que recorriera todos los nodos del grafo pasando una única vez por cada uno de ellos, entonces estaríamos ante lo que se denomina como camino o circuito hamiltoniano.

La determinación y búsqueda de caminos o circuitos eulerianos juega un papel fundamental en la resolución de distintos problemas que se plantean en diferentes disciplinas científicas y situaciones como… encontrar la salida de un laberinto.

Matemáticamente un laberinto es un grafo en el que los nodos son las estancias y cada pasadizo se representa mediante dos aristas entre los nodos correspondientes (una en cada sentido). Así se obtiene lo que se denomina grafo dirigido puesto que las aristas están dotadas de un sentido.

La condición establecida por Euler se puede reescribir en el caso de los grafos dirigidos diciendo que existe un circuito euleriano cuando el número de aristas que llegan a cada nodo coincide con el número de aristas que parten de él. Esto es precisamente lo que ocurre en el grafo dirigido que representa al laberinto. Así pues, es posible recorrer todas las estancias del mismo pasando por cada pasadizo una única vez en cada sentido. Consecuentemente, en algún momento de ese recorrido debemos encontrarnos con la salida.

Ahora bien, una vez que sabemos que dicho camino existe, sería necesario encontrar un procedimiento para recorrerlo de manera ordenada. En este sentido se han propuesto diferentes métodos en el supuesto de que nos encontráramos inicialmente dentro de un laberinto, en un lugar desconocido, y que no tuviéramos conocimiento del plano del mismo. El más sencillo es el propuesto por el matemático francés Gaston Tarry en 1895.

El algoritmo de Tarry se basa en la siguiente reflexión: cuando recorremos un laberinto y nos encontramos en un pasadizo inmediatamente antes de entrar en una estancia o inmediatamente después de dejar una estancia, el número de veces que hemos entrado en estancias –salvo la de partida- es el mismo que el número de veces que hemos salido de ellas (es decir, el número de aristas que hemos recorrido entrando en nodos debe ser igual al número de aristas que hemos recorrido saliendo de nodos). En consecuencia, una vez que hemos entrado en una estancia (y no la hemos abandonado) el número de aristas recorridas hacia un nodo (entrando en el nodo) es una unidad superior al número de aristas recorridas desde un nodo (saliendo del nodo). Teniendo en cuenta esto, Tarry se basó en la siguiente regla para diseñar su algoritmo: nunca recorras de nuevo un pasadizo que te haya llevado a una estancia por primera vez a menos que no exista alternativa. Así, el algoritmo propuesto por Tarry es como sigue:

-Cada vez que se entre por primera vez en un pasadizo debemos hacer dos marcas a la entrada del mismo.

-Cada vez que lleguemos a una estancia debemos dejar a la salida del pasadizo que nos ha conducido a ella una marca si dicha estancia ya ha sido visitada o tres marcas si no lo ha sido.

-Cada vez que salgamos de una estancia hemos de elegir los pasadizos inexplorados (no tienen marcas en su entrada) o aquellos que han sido recorridos en el sentido de entrada (poseen una marca).

Obsérvese que, si un pasadizo no tiene marcas a la entrada, está inexplorado y se puede recorrer. Si tiene una sola marca entonces ha sido utilizado para entrar en la estancia, luego puede usarse para salir de ella. Si tiene dos marcas no debe utilizarse pues ya se ha salido de la estancia por él previamente. Finalmente, si tiene tres marcas, fue el pasadizo que se utilizó para entrar por primera vez en la estancia y no debemos utilizarlo nuevamente a menos que el resto de los pasadizos que conduzcan a la estancia tengan también tres marcas.

Este algoritmo aparece (bajo ciertas licencias literarias referentes a su datación y eficacia) en la obra de Umberto Eco titulada “El nombre de la rosa” . En dicha novela, ambientada en el siglo XIV en una abadía benedictina situada en los Apeninos, se narran las aventuras detectivescas de fray Guillermo de Baskerville y su acompañante Adso de Melk. En ella se recoge el siguiente diálogo entre los dos protagonistas principales cuando se encuentran atrapados en la biblioteca de la abadía:

“— Sólo hay una manera -recitó, en efecto Guillermo- de encontrar la salida de un laberinto. Al llegar a cada nudo nuevo, o sea hasta el momento no visitado, se harán tres signos en el camino de llegada. Si se observan signos en alguno de los caminos del nudo, ello indicará que el mismo ya ha sido visitado, y entonces sólo se marcará un signo en el camino de llegada. Cuando todos los pasos de un nudo estén ya marcados, habrá que retroceder. Pero si todavía quedan uno o dos pasos sin marcar, se escogerá uno al azar, y se lo marcará con dos signos. Cuando se escoja un paso marcado con un solo signo, se marcarán dos más, para que ya tenga tres. Si al llegar a un nudo sólo se encuentran pasos marcados con tres signos, o sea, si no quedan pasos que aún falte marcar, ello indicará que ya se han recorrido todas las partes del laberinto.

— ¿Cómo lo sabéis? ¿Sois experto en laberintos?

— No, recito lo que dice un texto antiguo que leí en cierta ocasión

— ¿Y con esa regla se puede encontrar la salida?

— Que yo sepa, casi nunca. Pero igual probaremos (…)”

Ángel Martín del Rey es profesor de la Universidad de Salamanca y miembro de la Comisión de Divulgación de la Real Sociedad Matemática Española.

El ABCdario de las Matemáticas es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME).