Encontrar la salida a un laberinto en papel era un pasatiempo tradicional en nuestra niñez, pero su presencia es notable tanto en el mundo real —los jardines hechos laberinto son célebres— como en el de la ficción —con múltiples apariciones en novelas y películas—. Además de ello, estos problemas tan singulares tienen también su extensión en el mundo de la computación.
De hecho los algoritmos que resuelven laberintos son conocidos desde hace décadas y están muy relacionados con la teoría de grafos. Si te gustan este tipo de pasatiempos, hay diversos sitios web en los que es posible generarlos dinámicamente para luego imprimirlos y resolverlos.
Encuentra la salida (si puedes)
Los laberintos, de hecho, son también objeto de estudio en laboratorios científicos en los que los ratones han sido protagonistas. En esos estudios se realizan experimentos en el campo de la neurociencia con los que se busca entender mejor el aprendizaje espacial y la relevancia del hipocampo en este ámbito.
Su resolución es también un célebre campo matemático: Leonhard Euler fue uno de los primeros en analizar el problema desde ese punto de vista matemático y eso lo llevó a realizar contribuciones importantes al campo de la topología.
La teoría de grafos que está tan relacionada con este campo tiene una aplicación muy clara en nuestro día a día: el algoritmo de Dijkstra —también conocido como algoritmo de caminos mínimos— es el que usan tanto Google Maps como otros sistemas de navegación para determinar la ruta más corta a destino.
Para quienes tratan de resolverlos, el método más célebre para lograrlo es el llamado método de la mano derecha. Según este sistema no se debe separar la mano derecha de la primera pared que uno se encuentre.
Esa técnica tiene sus limitaciones, y ahí es donde entra una alternativa con más enjundia: el llamado algoritmo de Tremaux, que reduce de forma drástica el tiempo de resolución y que se basa en ir marcando los caminos que recorremos para no volver a repetirlos.
Hay otros algoritmos, desde luego, pero si lo que te gusta es resolver ese pasatiempo por ti mismo y buscar la salida a un laberinto, hay un buen número de generadores de laberintos que nos permiten configurar diversos parámetros para crearlos en pantalla y luego imprimirlos y resolverlos.
Estos generadores suelen ofrecer opciones como la forma del laberinto (circular, cuadrado, rectangular, hexagonal), la longitud de los lados o de las líneas, o los valores E ("Elitist tendency", cómo de corta es la solución en relación al tamaño del laberinto) y R ("River tendency", cuando más alto menos caminos condenados, pero estos son más largos)
Tenemos ejemplos como mazegenerator.net o mazegenerator.app, y en este último caso incluso es posible establecer una "semilla aleatoria" a partir de la cual se genera el laberinto, pero también podremos crear laberintos más coloridos que ojo, pueden engañar más que ayudar.
Otros son más sencillos en cuanto a las opciones de generación pero hacen algo curioso: muestran el camino de la entrada a la salida para demostrar que efectivamente estos laberintos tienen solución.
Hay otros generadores algo más intrincados: la comunidad Shadertoy, que reúne a desarrolladores que programan todo tipo de desarrollos haciendo uso de shaders, también tiene en su particular biblioteca una serie de generadores dinámicos de laberintos.
Aquí el manejo de las opciones es algo más confuso, y de hecho simplemente debemos editar alguno de los parámetros del programa para luego ver el resultado de la generación a la izquierda.
En este caso esa ventana se mantendrá siempre quieta: en otras creaciones de Shadertoy estos programas generan animaciones curiosas en las que esa ventana de reproducción cobra todo el sentido.
Y luego están otros laberintos, claro. En Xataka, por si no lo sabías, hace tiempo que mantenemos el podcast 'Laberinto de papel', dedicado a la literatura fantástica y de ciencia. Teníamos que decirlo.
Ver 1 comentarios