Sunday, July 06, 2014

Programación lúdica: generación de laberintos


Hay muchas tareas en programación que las consideramos sencillas… hasta que tenemos que programarlas. Una idea que lleva tiempo en mi cabeza es la que se refiere a la creación y resolución de laberintos. ¿Qué tan difícil será crear un laberinto y más aún, hacer un programa que dé con la solución?

Esta es pues el nuevo reto de la programación lúdica: Escríbase un programa que genere un laberinto, y además, lo resuelva satisfactoriamente. Las dos partes son obligatorias.

Para esto, es interesante entender algunas ideas sobre este tema. Dice la Wikipedia: “Un laberinto es un pasatiempo gráfico consistente en trazar una línea desde un punto de origen situado en el exterior de un laberinto a uno de destino situado generalmente en el centro o bien en el lado opuesto. La dificultad consiste en encontrar un camino directo hasta el lugar deseado. El laberinto, por su propia configuración, contiene diferentes vías sin salida (de mayor o menor longitud) y sólo un recorrido correcto. Puede adoptar diferentes formas: cuadrado, ovalado, redondo, cuadrangular, etcétera”.

Crear un laberinto se puede hacer de la siguiente manera:

Considérese que el laberinto es una cuadrícula de celdas. Con esto en mente, empiece en cualquier celda (al azar incluso). Marque la celda actual como visitada y obtenga una lista de sus vecinos. Para cada vecino, puede empezar con uno de ellos al azar y: si el vecino no ha sido visitado, quite la pared entre esta celda y la del vecino, y entonces recursivamente con ese vecino como la celda actual, genérese el mismo algoritmo para los otros vecinos. Desde luego es una sugerencia. Cada quien puede usar la técnica que deseé.

Este programa, probablemente puedan encontrarlo en la red. No se trata pues de copiarlo de algún sitio. Si descubro una copia o si tengo dudas, me tomo la libertad de preguntarle al autor directamente cómo hizo, para garantizar así que la solución fue escrita y no copiada por el autor del programa. Juguemos pues limpiamente y aprendamos todos de estos retos.


¿El premio? Una taza con el logotipo de la Morsa a la mejor solución, en donde los criterios serán qué tan versátil es el programa: ¿Puedo cambiar el tamaño del laberinto creado? ¿Es muy lento, es muy rápido? ¿Qué opciones da al usuario para la creación del laberinto? Cabe decir que no ganará el primero que envíe su solución (aunque en caso de tener que desempatar, se dará prioridad a quien lo haya entregado antes)



Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de 8 GBytes al menos y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero mientras no tengamos patrocinadores, esto es lo que hay.

¡A darle entonces!

3 comments:

Iván Martínez Cortés said...

Dice la Wikipedia: “Un laberinto es un pasatiempo gráfico consistente en trazar una línea desde un punto de origen situado en el exterior de un laberinto a uno de destino situado". ¿Algo que se autodefine o recursión?

Iván Martínez Cortés said...

Dice la Wikipedia: “Un laberinto es un pasatiempo gráfico consistente en trazar una línea desde un punto de origen situado en el exterior de un laberinto a uno de destino situado". ¿Algo que se autodefine o recursión?

Morsa said...

se puede definir recursivamente, sin duda