Alicatado Tetronimo con azulejos dados : Cómo eliminar los primeros casos en los que no existe solución

Question

He creado un solucionador de rompecabezas de bloques en javascript, que encuentra la solución al rompecabezas de bloques basado en el tetronimo en un tablero de tamaño X*Y definido por el usuario.

Mi problema es que me gustaría evitar el cálculo por completo si hay una fórmula matemática o algún enfoque que pueda determinar rápidamente si el rompecabezas es resoluble.

No tiene sentido malgastar la energía del ordenador en un proceso de fuerza bruta para probar todos los tetrominós si el tablero no tiene solución.

Así, por ejemplo, en este caso, he seleccionado 8 bloques: J,J,L,L,O,O,O y unas dimensiones de tablero de 8 x 4. He calculado la solución pasando por todas las combinaciones posibles. Del mismo modo, me gustaría saber de antemano que existe una solución.

El rompecabezas está disponible en GitHub como código abierto si alguien quiere contribuir directamente a la base de código: https://github.com/JozefJarosciak/TetronimoPuzzleSolver

Answer 1

En general, los problemas de mosaico de esta naturaleza son difíciles de calcular (no hay una respuesta "rápida"). No estoy 100% seguro de que no haya algún criterio para este problema exacto, pero me sorprendería que lo hubiera.

Aunque no pueda conocer la respuesta por completo de antemano, puede conocerla antes y, al menos, recortar algo de tiempo de ejecución.

Una idea es utilizar invariantes de color; no puedo decir cuán fructífero sería este enfoque, pero definitivamente lo investigaría.

Digamos que tenemos un $6 \times 6$ cuadrado, y tenemos 5 tetrominós T (cuya orientación no importa por ahora) y 4 cuadrados.

Ahora colorea el rectángulo con el colorido del tablero de ajedrez, y observa que un cuadrado siempre cubre 2 casillas blancas y 2 negras, y un tetrominó T cubre 3 blancas y una negra o 1 negra y 3 blancas. Así que tenemos dos tipos de tetrominós T y un tipo de cuadrado. Ahora dejemos que el número de cada uno de estos tres tipos en un mosaico se denote $T_1$ , $T_2$ y $S$ . Ahora podemos escribir un conjunto de ecuaciones para el número de casillas blancas y negras en términos de estos valores:

$$W = 2S + 3T_1 + T_2$$ $$B = 2S + T_1 + 3T_2$$

Pero sabemos que $S = 4$ y $W = B = 18$ , por lo que obtenemos

$$18 = 8 + 3T_1 + T_2$$ $$18 = 8 + T_1 + 3T_2$$

O después de un poco de álgebra,

$$T_1 = T_2$$

Pero sabemos que $T_1 + T_2 = 5$ por lo que no es posible realizar un mosaico (ya que $T_1$ y $T_2$ deben ser números enteros).

En este caso tenemos suerte y obtenemos una respuesta inmediatamente. Y esto también funcionará si sustituimos las casillas por cualquiera de las otras fichas (todas las demás fichas cubren 2 casillas negras y 2 blancas).

Para ver cómo esto puede acelerar el algoritmo, tomemos el mismo problema, pero digamos que elegimos 5 cuadrados y 4 T en su lugar. Supongamos ahora que el algoritmo llega a este mosaico parcial:

Ahora podemos podar las posiciones en las que el tetromino T caerá para cubrir 3 casillas negras, ya que sabemos que tales tilings son imposibles.

Por ejemplo, no necesitamos buscar tilings en los que el siguiente tetrominó T caiga en las posiciones rojas marcadas abajo:

El truco es, por supuesto, idear coloraciones que sean útiles para varios conjuntos de baldosas, y luego juntarlas en un algoritmo cohesivo. Otro ejemplo de una coloración potencialmente útil es la siguiente, que puede utilizarse para un conjunto de baldosas con barras y cuadrados.

Un cuadrado cubre 1 negro y 3 blancos, y hay dos barras que cubren 4 blancos, o 2 de cada uno. Esto nos da estas ecuaciones:

$$W = 3S + 4B_1 + 2B_2$$ $$B = 1S + 2B_2$$

Tendrá que jugar con varias coloraciones para ver cuáles son útiles. Por supuesto, también puedes encontrar coloraciones que funcionen para tres o más fichas. Sin embargo, también puede reducir el tiempo de búsqueda utilizando coloraciones para conjuntos de baldosas con dos baldosas si coloca primero las baldosas de un tipo. (Aunque esto puede afectar al algoritmo de otras maneras. Por ejemplo, si pruebas todas las posiciones de una baldosa determinada, puedes perder parte del beneficio de la aceleración de la aleatorización que obtienes).

También hay otras invariantes que puedes probar para acelerar las cosas. Por ejemplo, todos los lados convexos de un mosaico cuadrado deben tener una longitud uniforme. (Si colocas primero todas las demás baldosas, puedes podar algunas ramas del árbol de búsqueda con esta prueba).

Aunque este tipo de coloraciones suelen ser regulares en algún sentido, no es estrictamente necesario. El uso de un patrón facilita la reducción del número de tipos de fichas, pero también se puede hacer de otras maneras. (Por ejemplo, puede utilizar una coloración con la única restricción de que todas las celdas negras tengan sólo vecinos blancos. Con este esquema hay tres tipos de casillas: sólo blancas, una negra y tres blancas, y dos negras y dos blancas). Puede ser interesante ver si las coloraciones aleatorias con las restricciones adecuadas le dan un aumento de velocidad; si es así, no necesita buscar las específicas.

También puede consultar este documento, que puede contener otras (y más) ideas útiles: Invariantes de los azulejos de la cinta .