Resolviendo laberintos utilizando el programa Paint

Dibujo20130318 maze to be solved

Trata de resolver este laberinto (la entrada está en el lateral derecho, en la parte de arriba, y la salida en el lateral inferior, a la derecha). Imagina que copias esta figura en un programa de dibujo (como Paint de Windows). ¿Cómo podrías resolver este laberinto utilizando dicho programa? Piensa un poco, porque es muy fácil. Si al final no logras resolverlo, sigue este enlace para ver la solución. Por supuesto, este método gráfico es muy viejo, fue publicado por E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1: 269-271, 1959 [copias gratis en pdf]. Quien prefiera una explicación for dummies (de donde he sacado este ejemplo) y una implementación en Matlab preferirá leer a Cris Luengo, “Solving mazes using image analysis,” Cris’s Image Analysis Blog, April 17, 2010.

PS: Quien quiera probar que el método funciona, en lugar de usar el laberinto en JPG como aparece en la entrada, debería utilizar la versión en PNG (sigue este enlace) [solución en PNG].

Anuncios

7 pensamientos en “Resolviendo laberintos utilizando el programa Paint

  1. Sin hacer trampas, se me ocurre aprovechar la capacidad del programa para manchar áreas delimitadas por frontera de otro color. Derramaría la tinta en el blanco de la entrada, y eso me delimitará la zona que conecta con la salida.

    • ¡Uy! Ahora que he mirado la solución, parece que se tiñen los muros del laberinto desde la entrada. No sé si mi idea funcionaría igualmente, aunque ahora que lo pienso mejor, igual acabo inundando todo el laberinto, pues puede que existan zonas con puerta de entrada sin otra de salida. Lástima, de repente pensé que era yo uno de esos chicos listos.

      • Tu estrategia sirve para acotar una solución, por ejemplo, supongamos que las paredes del laberinto son de diferentes colores, pero el suelo es siempre del mismo color, entonces no se puede usar la estrategia del post, pero sí una variante de la tuya.

        La variante es la siguiente: si te encuentras con una bifurcación, estarás en duda de si ir por una bifurcación o por la otra, tapas una de ellas y rellenas la otra, si el relleno llega al destino has tapado bien, sino, deshaz porque es el otro camino.

        Repite el proceso hasta llegar a la salida.

        El proceso “sólo” hay que hacerlo tantas veces como bifurcaciones no triviales tenga la ruta final de salida.

  2. Aparte de la solución de teñir muros,etc., otra: Ya que disponemos de un programa de dibujo y el laberinto es un dibujo, se trazán unas lineas paralelas desde la entrada a la salida, se rellenan de blanco y ya está. :)

Los comentarios están cerrados.