Esta es una práctica que realicé (y comenté) en diciembre de 2008 para la asignatura de Programación III de la UNED.
La práctica se basaba en realizar un sistema para resolver tableros de shikaku, mediante el algoritmo de vuelta atrás. Mi solución es óptima pero no del todo correcta desde un punto de vista académico, ya que el uso del algoritmo (de backtracking) es menos usado de lo que debería.
Para poder ver el código, este puede descargarse a través de un cliente de Subversion, en sistemas Unix/Linux es tan fácil como:
svn co http://project.bosqueviejo.net/svn/shikaku/trunk
Explicación del código
Bueno, tengo que reconocer que, después de algo más de un año de haberlo hecho, he tenido que releer y revisar de nuevo todo para acordarme (y reaprender) cómo hace lo que hace.
Por ello, voy a escribir una documentación básica sobre el código en sí, para tenerla como referencia, cuando tenga que volver al mismo otra vez, y para que sirva a todos aquellos que lo necesiten.
En principio, el código se divide en las siguientes clases:
- shikaku.tablero.Combinacion: esta clase se encarga de almacenar combinaciones. Una combinación es un rectángulo que se sitúa ocupando un espacio de X*Y=N. La combinación debe de tener en alguna de sus casillas el número contenido, por lo que se almacena también la ordenada de N para comprobaciones.
- shikaku.tablero.Ordenada: es cada uno de los números que aparecen en el tablero. Se almacena su posición dentro del tablero y la representación numérica del mismo.
- shikaku.tablero.Tablero: almacena las dimensiones del tablero, la lista de combinaciones fijas (las que solo tienen una combinación válida detectada) y la lista de soluciones posibles para el tablero.
Una ejecución de shikaku tiene los siguientes pasos:
- Entra en main de la clase shikaku, donde se detecta el origen de datos, hasta saber de donde se va a cargar el tablero.
- En run se crea una instancia del tablero, y se ejecuta, para cada punto del tablero, el generador de la clase Combinacion.
- El generador se encarga de buscar combinaciones válidas para el punto dado, dentro del tablero y validando su posición dentro del tablero (es decir, que no haya parte del rectángulo fuera) y con respecto al resto de puntos (que no tenga contenido nada más que el punto del que tiene que hacer la combinación).
- El último paso para la resolución, es llamando a buscaSoluciones, de la clase Tablero, que se encarga de realizar el algoritmo de vuelta atrás para buscar las soluciones al tablero.
Estos son los pasos más importantes dentro del código para resolver el tablero de shikaku.
La depuración
Uno de los motivos por los que el algoritmo no es del todo de tipo vuelta atrás, es precisamente por el uso de tres algoritmos voraces que se ejecutan antes que el último, de vuelta atrás. Estos algoritmos realizan una criba sobre las combinaciones basándose en tres premisas que debe cumplir cada combinación para ser válida:
- Que no haya nada fuera del tablero: esto se realiza mediante una simple validación a la hora de generar las combinaciones. Es simple y rápida, y quita mucho procesamiento al algoritmo final.
- Combinaciones con un solo número: esto se refiere a que dentro del rectángulo que conforma la combinación, solo esté contenido el número objeto de la combinación y ningún otro. Esta validación también está incluida a la hora de generar las combinaciones, para lo que se necesita, en el generador, pasar todos los puntos del tablero.
- Eliminar combinaciones imposibles: imposibles, además de las que se descartan en los puntos anteriores, son las que colisionan con todas y cada una de las combinaciones posibles de otro número vecino. Si la combinación de un número colisiona con todas las combinaciones posibles de otro número, como es lógico, no podrá ser posible.
Ciertamente, con estos algoritmos se llega a resolver un alto porcentaje de los tableros básicos, sin necesidad de realizar el algoritmo de vuelta atrás. Solo los tableros grandes y con dificultad alta, necesitan, además de estos algoritmos voraces, el de vuelta atrás.
Mejoras
En sentido académico, teniendo en cuenta uno de los requisitos que se pide, que es que sea un algoritmo de vuelta atrás, quizás sea más correcto que la depuradora actúe solo a nivel de rama y no en profundidad.
Hay que tener en cuenta que esto penalizaría el rendimiento y empeoraría en lo que a gestión de memoria se refiere, pero prima más cumplir con los requisitos 
Loading ...
Hola Manuel,
Buscando info sobre Programación III de la UNED en google, me he encontrado con tu web. Quería felicitarte por tu blog, está muy currado. Por lo que he leído parece que empezaste en el plan anterior al grado, y luego te pasaste, convalidando me imagino. Yo estoy aún en el antiguo y quería pasarme dentro de un año al grado convalidando y no sé si coger Programación III puesto que he leído que abarca mucho tiempo y no dispongo de tanto. Me puedes orientar en tu caso sobre el tiempo, dificultad etc que te ha supuesto Programación III?
Gracias
Saludos
[ Responder ]
bombadil Respuesta:
Usandomayo 23rd, 2011, %H:%M 12Mon, 23 May 2011 12:55:14 +000014.
En mi caso, Programación III fue un hueso muy duro… por otros motivos no me pude presentar al examen, por lo que me quedé con la práctica aprobada y el examen sin hacer… pero bueno, el problema, es que la programación está vista desde su lado más matemático, analizando el coste computacional de cada bucle, instrucción, recursividad…
En mi opinión, como cada lenguaje está implementado de una forma diferente, y hay elementos que optimizan muchas cosas que se escriben, para que se ejecuten de una forma mucho más óptima, lo que es el coste computacional, solo te sirve a nivel informativo, si vas a desarrollar, para que tengas en cuenta y siempre presente que una estructura puede ser más “costosa” que otra a la hora de desarrollar… pero claro, hay muchas excepciones, y las matemáticas no las tienen en cuenta, ya que, no todas las instrucciones se ejecutan en el mismo tiempo, y dependiendo de una implementación u otra, puede que hagas que, en la que en el papel sea más ligera, en la práctica sea más pesada porque la línea que se ejecuta más, sea la más pesada de todas, mientras que en otras implementaciones, ejecutándose menos esa y 10 veces más otras, esa forma sea más ligera.
Se ve que esto se ha tenido en cuenta y esta asignatura fue suprimida en favor de otras, como Programación Orientada a Objetos.
Sobre lo del Grado, te recomiendo que te cambies, son menos asignaturas y tendrías la categoría de Ingeniero, directamente. Sobre el discurso de que haciendo menos años se es “menos profesional”, o se pierde en gran medida la cantidad de información que se daba antes… te puedo decir que es mentira, ya que las asignaturas que se han “eliminado” han sido en gran medida las que NO usamos los informáticos. Así, además, se han agregado otras que SÍ nos vienen muy bien
¡Ah!, y gracias por el cometnario
[ Responder ]
Muchas gracias Manuel!!
Un saludo
[ Responder ]