Después del parón de los exámenes volvemos a la carga. En este caso, voy a publicar la práctica de una asignatura de la carrera. El enunciado de la práctica consiste en resolver el problema del Trimino, que se trata de un tablero de X*X tamaño, siendo X una potencia de 2, y teniendo una casilla marcada. Entonces debemos recubrir el tablero utilizando triminos (un angulo de tres casillas). Una descripción más detallada del problema con su solución teórica la podemos encontrar en el siguiente enlace : http://www.dma.fi.upm.es/docencia/primerciclo/matrecreativa/juegos/poliominos/triminos/triminos.htm

Para la solución del problema se puede utilizar uno de los esquemas algorítmicos básicos, en este caso el esquema de Divide y Venceras. Que comentado por encima, consiste en coger un problema y dividirlo en partes iguales y más sencillas, hasta llegar a una solución trivial. Una vez llegada a esta solución, se va juntando las soluciones parciales para llegar a una solución completa.
La adaptación de mi esquema para este problema es el siguiente:


public static void divide(Rectangulo r){
boolean b=buscarLleno(r);
if(b) // comprobacion de si es el caso trivial
return;
// Division en subproblemas
ArrayList<Rectangulo> rects = r.dividirEnCuatro();
for(Rectangulo r1  : rects){
divide(r1); // Llamada recursiva para resolver el subproblema
}
 }

Gracias a la mayoría de las funciones auxiliares, el algoritmo  resultante es muy reducido. Pinchando aquí os podeis descargar la práctica resuelta. Podesi descargarlo de github: https://github.com/smaug1985/Trimino

« »