Resolviendo Shikaku

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:

1. Entra en main de la clase shikaku, donde se detecta el origen de datos, hasta saber de donde se va a cargar el tablero.
2. En run se crea una instancia del tablero, y se ejecuta, para cada punto del tablero, el generador de la clase Combinacion.
3. 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).
4. 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:

1. 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.
2. 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.
3. 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 ;-)