Hace tiempo practicaba (yo) una actividad para pasar el tiempo, en aquellos momentos cuando no tenía qué hacer (bueno, sí tenía, pero era aquella época del año en que preferías hacer otras cosas antes que estudiar para los exámenes. Cuántas cosas tuvieron origen en las pocas ganas de estudiar que tenía alguien; este mismo weblog, sin ir más lejos. Pero me estoy desviando del tema…). Esta actividad era la elaboración de laberintos.
No resolverlos, ojo: inventárselos.
Unos años antes ya tenía afición por esta cosa de los laberintos, pero los hacía de modo artesanal, por así decirlo; en una hoja cuadriculada trazaba el camino “solución”, dejando huecos a derecha e izquierda del intrincado pasillo para los caminos que te despistaban; sin embargo, la única dificultad consistía en encontrar el camino sin tardar mucho, porque había varias soluciones.
Sin embargo, gracias a la asignatura de Matemática Discreta (de 1º de carrera), pude hallar la solución científica (y aquí imagínense un relámpago con su correspondiente trueno).
Para explicar la solución científica, sin embargo, antes tengo que explicar algo de teoría de grafos. No se asusten, que es simple: un grafo es un conjunto de puntos (nodos) unidos por líneas (aristas). Ya está. Los matemáticos dicen que un grafo G es un par formado por un conjunto N de nodos y un conjunto E de aristas, y luego se ponen a definir las aristas, y… pero al final viene a ser lo mismo, sólo que más formal.
De la definición de grafo luego sacan la definición de árbol. No un árbol de estos con tronco leñoso, sino un árbol matemático: es un grafo hecho de tal manera que entre dos nodos cualesquiera hay un camino y sólo un camino.
Me siguen, ¿no? ¿A que no ha sido tan terrible? Pues la gracia del asunto es que si se dibuja un laberinto en papel cuadriculado, haciendo que las paredes sigan las rayas de la cuadrícula, se puede considerar que este laberinto es un árbol. Sólo hay que imaginarse que cada casilla es un nodo de un grafo y que cada punto del laberinto por el que se puede pasar de una casilla a otra es una arista que va del nodo que representa a la primera casilla al nodo que representa la segunda.
Entonces, para hacer un laberinto basta con hacer un árbol sobre papel cuadriculado, uniendo los centros de las casillas; una vez hecho, se trazan paredes sobre los lados de las casillas por los que no crucen aristas, y listo.
Para hacerlo por ordenador bastaría con comenzar teniendo cada nodo perteneciendo a una “clase” distinta; por ejemplo, etiquetar cada una de ellas con un número o un color diferente. A partir de entonces, se empezaría a unir nodos siguiendo estas tres reglas:
De este modo, cuando ya no se pueda seguir este proceso, se tendrá un árbol en el interior del laberinto; bastará entonces con dibujar una entrada y una salida, y pintar las paredes.
Hay otro método, que no es tan matemático ni tan científico, pero es igual de útil y es más fácil de emplear por parte de los humanos, pero ese método lo explicaré otro día.