Autor
Para el que no sepa de que va la cosa, se trata de un tablero rectangular (o cuadrado) vacío y se dispone de varias piezas de tetris que colocadas de una forma determinada llenan todo el tablero.
Ayer me aburrí de probar distintas disposiciones de piezas en el minijuego de tetris de The Talos principle y hoy he creado un programa que resuelve el juego. La solución está basa en backtracking:
- unas cuantas funciones para manipular las piezas y cargar las condiciones del juego...
- una funcion que decide si es correcto o no poner una pieza en una posicion dada
- una funcion recursiva que soluciona probando para cada uno de los giros posibles de las piezas todas las posiciones del tablero en las que cabe.
Para tableros no muy grandes, entre unas 20-36 casillas y no más de 10 piezas, la solución normalmente no tarda nada, o en algún caso raro tarda algunos segundos, pero si pasamos a tableros con más datos, en algún caso después de media hora de ejecución todavía no ha encontrado la solución.
La verdad es que ya estoy cansado de código por hoy. Quería pediros que si se os ocurren condiciones nuevas, por ejemplo que descarten callejones sin salida, para añadir a la función que detecta la corrección, o si conocéis o se os ocurre algún método eurístico para buscar posiciones iniciales más óptimas de las piezas que me lo digáis, o si queréis modificad el código que os dejo en el enlace y compartidlo por aquí.
Podéis descargar el código desde aquí. Creo que se entiende bien, pero si no lo entiendo yo que soy el que lo ha escrito mal vamos, si no entendéis algo o hace falta introducir más comentarios avisad y actualizo el enlace.
¡Saludos!
Enlace actualizado: Alguna pincelada en main y ahora las piezas guardan la posición fila-columna en la que se han colocado por si una vez resuelto se quiere representar de alguna forma menos cutre que la actual (mensaje para los que manejan SDL, Allego u otra librería gráfica
) y se ha añadido una función para comprobar si un hueco en el tablero está formado por menos de cuatro casillas vacías, en cuyo caso, al no caber ninguna pieza en ese hueco, se vuelve atrás en la función recursiva que busca la solución. El algoritmo ha mejorado, con el juego del ejemplo 2 la solución es instantánea. Podéis comprobar la diferencia comentando y descomentando la parte:Código
en la función resolver.
Se me olvidaba. El programa funciona por línea de comandos. La sintaxis es nombre_programa fichero1 [fichero2 ... ficheroN]
Cada uno de los ficheros tiene que contener un juego con la siguiente información:
1ª línea: Numero de filas del tablero.
2ª línea: Numero de columnas del tablero
3ª línea: Numero de piezas.
- Tantas líneas como numero de piezas y en cada una de ellas el nombre de una de las piezas del juego (CUADRADO, L_NORMAL, L_SIMETRICA, T, Z_NORMAL, Z_SIMETRICA o BARRA)
Por ejemplo:
Código:
8
5
10
2 Z_NORMAL
1 Z_SIMETRICA
2 T
2 BARRA
2 L_NORMAL
1 CUADRADO
Ejemplo 2:
Código:
8
7
14
2 T
4 Z_NORMAL
2 Z_SIMETRICA
3 L_NORMAL
3 L_SIMETRICA
La leyenda de la solución es:
C-Cuadrado:
Código:
**
**
L-L normal en alguno de sus giros:
Código:
*
*
**
l-L simétrica en alguno de sus giros:
Código:
*
*
**
T:
Código:
***
*
Z:
Código:
**
**
z:
Código:
**
**
-, barra:
Código:
****
Sigo con el culebrón. Al final la versión en la que utilizaba un árbol para almacenar las situaciones que no llevaban a ninguna solución ha resultado ser mucho mas lenta, así que en el enlace inicial dejo la última solución que tengo.
De todas formas, tengo pendiente un algoritmo en el que para tablas grandes, de más de 60 casillas (15 piezas), trocee la tabla en fragmentos más pequeños para intentar solucionarlos y luego solapar las distintas soluciones. Si me da por hacerlo y consigo algo mejor que lo actual colgaré el código por aquí.
Por cierto, he modificado el formato de los archivos para que queden más compactos. Ahora las filas con las piezas contienen pares Repeticiones-Nombre de la pieza, que indican, como bien habréis deducido, el número de veces que se repite cada pieza.
El primero de los siguientes ejemplos, 15 piezas (60 casillas) se resuelve, en un Intel Core 2 Duo viejete, en un poco más de 9 segundos, el segundo, 64 casillas y 16 piezas, en 11 minutos y 3 segundos y el tercero, con 33 piezas, ni idea, pero mejor ni lo intento.
Código:
6
10
15
2 Z_NORMAL
3 L_NORMAL
4 T
3 Z_SIMETRICA
3 L_SIMETRICA
Código:
8
8
16
5 Z_SIMETRICA
1 Z_NORMAL
1 L_NORMAL
3 L_SIMETRICA
6 T
Código:
11
12
33
4 Z_SIMETRICA
11 L_SIMETRICA
4 T
2 Z_NORMAL
12 L_NORMAL
Hola otra vez. Aquí os dejo el último código que tengo. Esta vez repartido en varios ficheros fuente.
La idea esta vez es, en lugar de resolver el puzzle completo con todas las piezas, delimitar sectores con una cantidad determinada de filas y columnas, como si fuesen baldosas que cubren el tablero de juego, e intentar resolver cada uno de ellos por completo, sin tener en cuenta que por los bordes sobresalgan las piezas, pues el propio algoritmo se encargara de rellenas los huecos que queden al llegar al sector hacia el que sobresalgan.
La línea de comandos queda:
nombre_programa filasxsector columnasxsector fichero1 [fichero2 ... ficheroN]
En cuanto a tiempos de ejecución el resultado ha sido muy irregular.
Los mejores resultados los he obtenido con sectores 2x2 y aumentar el numero de filas o columnas por sector hace que los tiempos de ejecución se disparen. Por ejemplo, con sectores 2x2, de los tres juegos anteriores el primero ha pasado a resolverse en 0'0037 segundos, el segundo en 3'731 segundos y el tercero sigo sin saber cuanto tiempo le cuesta, porque me aburro de esperar y lo corto.
Pero por ejemplo, el juego que muestro a continuación, con el algoritmo del primer enlace se resuelve en 0'026 segundos, pero con el nuevo algoritmo y siendo que el tablero es de menor tamaño que cualquiera de los tres anteriores (y por lo tanto con menos piezas) tarda 4 minutos y 21 segundos en resolverlo:
Código:
8
7
14
2 T
4 Z_NORMAL
2 Z_SIMETRICA
3 L_NORMAL
3 L_SIMETRICA
Yo solo usaría este nuevo código para puzzles de más de 14-15 piezas y solo por si hay suerte y lo resuelve en un tiempo relativamente razonable.
Hasta aquí ha llegado mi aventura con este problema. Si alguien puede mejorar alguno de los dos algoritmos que lo haga y nos deje las mejoras por aquí, o si encuentra uno mejor y puede hacérmelo llegar se lo agradecería, pero lo que es por mi parte, abandono, tengo mejores cosas que hacer que estar perdiendo el tiempo con esto.
¡Buenas!
Hay veces que parezco tonto. Me acabo de dar cuenta de que los huecos inútiles no son aquellos con una cantidad de espacios menor que tres, sino los que no tienen una cantidad de espacios que sea múltiplo de cuatro.
He corregido el código y he actualizado los enlaces. No esperéis que los puzzles que antes no resolvían en un tiempo razonable ahora si lo hagan, simplemente han mejorado algo los tiempos de los puzzles que ya se podían resolver.
Por cierto, jugando un poco con las dimensiones de las celdas os podéis llevar alguna sorpresa. Por ejemplo, en el último ejemplo que he colgado con sectores 3x5 la solución es casi inmediata (0'225 segundos en mi caso)
¡Saludos!
Ya se que dije que iba a dejar el tema, pero no he podido hacerlo, y por fin tengo una solución que mejora, y mucho, las anteriores.
La idea esta vez ha sido ir llenando primero los huecos más pequeños, valorando cada una de las casillas vacías de forma que guarden el numero de casillas vacías que haya en el hueco en el que se encuentra... lío. Mejor lo pongo con un ejemplo:
Código:
123456
------
1|
2| **
3| **
4|
5|
En la segunda fila vemos que hay dos espacios, una pieza y después otros dos espacios libres, así que las dos primeras casillas indican que están en una fila de un hueco, y que el hueco en esa fila tiene dos espacios horizontales libre. Lo mismo con las dos últimas casillas.
En la tercera columna hay un espacio vacío, una pieza y tres espacios vacíos más, así que la primera casilla tendrá un uno como espacio vertical y las casillas 3, 4 y 5 un tres como valor de espacio vertical, ya que la columna en la que se encuentran está en un hueco de 3 espacios.
Una vez que se ha asignado a cada casilla vacía el espacio vertical y horizontal, buscamos la que tenga el valor más pequeño (da lo mismo que sea vertical u horizontal, ya que buscamos el hueco más pequeño), e intentamos rellenarlo con los distintos tipos de pieza que queden por usar (fuerza bruta para rellenar el hueco, vamos).
Aquí os dejo el último código. Como ejemplo, el siguiente puzzle lo resuelve, en mi ordenador, en unos dos minutos y medio. La mejora con respecto a los algoritmos anteriores es muy grande.
Código:
11
12
33
4 Z_SIMETRICA
11 L_SIMETRICA
4 T
2 Z_NORMAL
12 L_NORMAL
Ahora que he llegado a este resultado si que doy el tema por zanjado.
¡Saludos!
Hala, ahora si que paro con el tema. XD
El enlace al código definitivo.
Acabo de añadir una función que da "color" a la solución. Realmente lo que se hace es asignar al campo color del struct Pieza el índice de un color dentro de una paleta de colores. He decidido no incluir el código que da "color" directamente a la solución dentro de la funcion colorear_solucion para que el código sea independiente de cualquier sistema de representación de los datos. La contrapartida de esta independencia es que la persona que vaya a usar el código tiene que crear la paleta de colores (en este caso un conjunto de cuatro caracteres) y luego tiene que acceder a los campos que correspondan en las estructuras de datos para poder crear su propia representación de la solución. En main hay un ejemplo sobre como hacerlo.
Como en linux los caracteres bonitos para dibujar las piezas salen como interrogantes he tenido que recurrir a x, o, + y *. Los que uséis Windows podéis imprimir los caracteres de la tabla ASCII en la forma valor-caracter y veréis que hay caracteres cuadrados con distintos dibujos que podéis usar para hacer que la representación quede más bonita.
Enlace actualizado: he econtrado algún error en el código que podía hacer que el programa cascase.
En línea
