Por Freddy
Solución a "Ubongo 3D"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Miguel Covarrubias Fuente: Miguel Covarrubias
La solución pone piezas de manera recursiva mientras quepan en el tablero y no se empalmen.
resuelve(pieza)
si pieza > P
regresa “Si”
para cada rotación de la pieza
para cada casilla g del tablero
para cada cubo c de la pieza
si al poner c sobre g, la pieza queda dentro de los primeros 2 niveles del tablero y no se empalma con otra pieza ya puesta entonces
marca las posiciones de los cubos de la pieza como ocupados
resuelve(pieza + 1)
desmarca los cubos de la pieza
Para rotar una pieza se puede rotar por $latex 0^o$, $latex 90^o$, $latex 180^o$ o $latex 270^o$ alrededor de cada eje. El número de operaciones es aproximadamente (número de rotaciones * número de casillas del tablero * número de cubos de una pieza)$latex ^3 \le (24 * 7 * 5)^3 < 600,000,000$. En los casos de prueba y en el juego todas las soluciones tocan la base del tablero, si no fuera así, solo hay que duplicar el 7 a 14. Para checar si una pieza se puede poner en cierta posición se pueden usar mascaras de bits para los niveles del tablero y para las posiciones ocupadas. Para poner la última pieza se puede comparar todas las rotaciones de los cubos no ocupados contra la última pieza y la complejidad cubica de la solución se reduce a cuadrática.