An Integer Linear Programming Model for the Evolomino Puzzle

Each language version is independently generated for its own context, not a direct translation.

¡Hola! Imagina que acabas de encontrar un nuevo juego de lápiz y papel, como un Sudoku o un "Nonogramas", pero con una mecánica muy especial llamada Evolomino.

Este artículo de investigación es como un "manual de ingeniería" para enseñarle a una computadora cómo resolver y crear estos rompecabezas. Aquí te explico de qué trata, usando analogías sencillas:

1. ¿Qué es el juego Evolomino?

Imagina un tablero de cuadrícula con algunas casillas sombreadas (como obstáculos) y otras blancas. En algunas casillas blancas hay flechas dibujadas.

La misión: Tienes que dibujar cuadrados en las casillas blancas para formar "bloques" (como piezas de Tetris).
La regla de oro: Cada bloque debe tener una flecha dentro.
La evolución: Las flechas no son solo decorativas. Dicen que los bloques deben "evolucionar". Imagina que el primer bloque es una pequeña semilla. El siguiente bloque en la misma flecha debe ser una copia exacta de la semilla, pero agregándole una nueva hoja (un cuadrado más). Y así sucesivamente: el tercer bloque es el segundo más una hoja, el cuarto es el tercero más una hoja, etc.
El reto: No puedes rotar ni girar las piezas; solo puedes hacerlas crecer en tamaño manteniendo su forma original.

2. El problema: ¿Cómo le explicamos esto a una computadora?

A los humanos nos gusta adivinar y probar, pero a las computadoras les gusta seguir reglas matemáticas estrictas. Los autores del artículo (dos matemáticos rusos) decidieron traducir las reglas de este juego a un lenguaje que la computadora entiende perfectamente: la Programación Lineal Entera (ILP).

Piensa en el ILP como un chef muy estricto que tiene una lista de ingredientes (las casillas del tablero) y una receta con reglas muy específicas:

"Si pones un cuadrado aquí, no puede haber otro al lado".
"Si el bloque 1 tiene 2 cuadrados, el bloque 2 debe tener exactamente 3".
"Todos los cuadrados de un bloque deben estar conectados, como una cadena de imanes".

El modelo matemático crea miles de estas "reglas" (ecuaciones) para que la computadora no tenga que adivinar, sino que simplemente busque la única combinación que cumpla con todas las reglas al mismo tiempo.

3. La magia de la "Corriente" (Conectividad)

Una de las partes más interesantes del artículo es cómo aseguran que los bloques no se rompan en pedazos. Imagina que cada bloque es una ciudad pequeña.

Los autores usan un modelo de "flujo" (como agua o electricidad).
Imagina que en el centro del bloque hay una presa que suelta agua.
El agua debe fluir por todas las casillas del bloque para llenarlas.
Si el bloque está roto (tiene dos partes separadas), el agua no llegará a la parte aislada. La computadora detecta esto y descarta esa solución. ¡Es como verificar que todos los habitantes de la ciudad estén conectados por carreteras!

4. Creando nuevos rompecabezas (El Generador)

No solo resolvieron el juego, ¡también crearon un robot constructor!
Usaron su modelo matemático para generar miles de rompecabezas nuevos. El proceso es así:

El robot dibuja flechas al azar en un tablero vacío.
Luego, "siembra" los bloques siguiendo las reglas de evolución.
Finalmente, borra pistas (cuadrados y sombras) poco a poco, verificando cada vez que solo quede una única solución posible.
Es como un jardinero que planta un bosque y luego poda las ramas hasta dejar solo el diseño perfecto que no deja lugar a dudas.

5. ¿Qué tan rápido es?

Pusieron a prueba a su "chef" (una computadora con un programa avanzado llamado CP-SAT) contra rompecabezas de diferentes tamaños:

Tableros pequeños (11x11): La computadora los resuelve en menos de un segundo. ¡Más rápido que parpadear!
Tableros grandes (18x18): Tarda unos 48 segundos.
El límite: Para tableros gigantes, el número de reglas matemáticas crece tan rápido (como una bola de nieve rodando por una montaña) que se vuelve muy difícil, pero la computadora sigue siendo muy eficiente.

En resumen

Este artículo es un puente entre un juego divertido de papel y lápiz y la matemática avanzada. Los autores tomaron un rompecabezas nuevo, le dieron una "traducción" matemática para que una computadora pudiera entenderlo, crearon un algoritmo para fabricar miles de niveles nuevos y demostraron que, con la tecnología actual, podemos resolver estos acertijos lógicos casi instantáneamente.

Es como si hubieran enseñado a una computadora a jugar al "Tetris evolutivo" y a diseñar sus propios niveles, todo usando un lenguaje de reglas estrictas.

Each language version is independently generated for its own context, not a direct translation.

Aquí presento un resumen técnico detallado del artículo "An Integer Linear Programming Model for the Evolomino Puzzle" (Un modelo de programación lineal entera para el rompecabezas Evolomino), escrito por Andrei V. Nikolaev y Yuri A. Myasnikov.

1. El Problema: Evolomino

El Evolomino es un rompecabezas lógico de lápiz y papel publicado recientemente (marzo de 2023) por la empresa japonesa Nikoli. Se juega en una cuadrícula rectangular con celdas blancas y sombreadas.

Mecánica principal: El jugador debe dibujar cuadrados en ciertas celdas blancas para formar bloques poliominoes.
Reglas clave:
1. Cada bloque debe contener exactamente un cuadrado colocado sobre una flecha pre-dibujada.
2. Cada flecha debe atravesar al menos dos bloques.
3. Evolución: Los bloques a lo largo de la ruta de una flecha deben "evolucionar". El segundo y siguientes bloques se forman añadiendo exactamente un cuadrado al bloque anterior, sin rotar ni girar el poliomino.
4. Los bloques deben ser poliominoes conectados (ortogonalmente).
Complejidad computacional: Se ha demostrado que decidir si existe una solución válida es NP-completo y contar el número de soluciones es #P-completo.

2. Metodología: Modelo de Programación Lineal Entera (ILP)

Los autores formalizan las reglas del juego mediante un modelo de Programación Lineal Entera (ILP). El objetivo es traducir las restricciones lógicas y geométricas en ecuaciones lineales que los solucionadores modernos puedan procesar.

Variables del Modelo

El modelo introduce tres tipos principales de variables para una cuadrícula de celdas $C$ , un conjunto de flechas $A$ , y un número máximo de bloques $K_a$ por flecha:

Variables de celda ( $x_i$ ): Binarias (1 si hay un cuadrado, 0 si no). Codifican el tablero inicial y la solución final.
Variables de bloque ( $y_{i}^{a,k}$ ): Binarias. Indican si la celda $i$ pertenece al bloque $k$ de la flecha $a$ .
Variables de activación de bloque ( $b_{a,k}$ ): Binarias. Indican si el bloque $k$ de la flecha $a$ existe.
Variables de flujo ( $f_{ij}^{a,k}$ ): Enteras. Utilizadas para garantizar la conectividad del poliomino.
Variables de traducción ( $t_{j}^{a,k}$ ): Binarias. Indican el desplazamiento (shift) entre el bloque $k-1$ y el bloque $k$ .

Restricciones Principales

El modelo se estructura en cuatro grupos de restricciones:

Restricciones Básicas:
- Cada cuadrado pertenece a exactamente un bloque.
- No se pueden colocar cuadrados consecutivos a lo largo de una flecha.
- Los bloques deben activarse secuencialmente (el bloque $k$ no puede existir si $k-1$ no existe).
- El tamaño del bloque $k$ debe ser exactamente uno mayor que el del bloque $k-1$ ( $N_{a,k} = N_{a,k-1} + 1$ ).
Conectividad (Modelo de Flujo):
- Se adapta un modelo de flujo basado en Gavish y Graves. Se asigna una fuente en la celda que contiene la flecha.
- El flujo debe distribuirse a todas las celdas del bloque. Si un bloque tiene componentes desconectados, las restricciones de conservación de flujo no se satisfarán.
Evolución de Bloques (Consistencia Geométrica):
- Se utilizan variables de traducción para asegurar que el bloque $k$ contenga una copia exacta del bloque $k-1$ desplazada, sin rotación ni reflexión.
- Las restricciones garantizan que si una celda pertenece al bloque anterior, su posición traducida debe pertenecer al bloque actual.
Consistencia de Celdas Adyacentes:
- Dos celdas adyacentes no pueden pertenecer a bloques diferentes (para evitar que polinomios de diferentes flechas se toquen incorrectamente).

Escalabilidad del Modelo

El número de variables es $O(K \cdot |C|)$ , donde $K$ es el número total de bloques y $|C|$ el tamaño de la cuadrícula. El número de restricciones es $O(K \cdot |C|^2)$ , dominado por las restricciones de correspondencia geométrica durante la evolución de los bloques.

3. Generación de Instancias

Para evaluar el modelo, los autores desarrollaron un algoritmo para generar instancias aleatorias de Evolomino con solución única:

Construcción: Comienza con una cuadrícula vacía y añade flechas mediante un "paseo aleatorio sesgado" (preferencia por continuar recto).
Colocación de Bloques: Para cada flecha, se colocan bloques evolutivos aleatoriamente, respetando las reglas de crecimiento y conectividad.
Minimización de Pistas (Carving): Una vez fijada una solución única, el algoritmo elimina iterativamente pistas (cuadrados y celdas sombreadas) en orden aleatorio. Si la eliminación crea una solución alternativa (verificado ejecutando el solucionador ILP), la pista se restaura. Esto garantiza un conjunto mínimo de pistas.

4. Resultados Computacionales

Los experimentos se realizaron utilizando la biblioteca Google OR-Tools (versión 9.15) en un equipo con CPU Intel Core i7-13620H y 16 GB de RAM.

Comparativa de Solucionadores: Se probaron cuatro solucionadores (CP-SAT, SCIP, CBC, BOP) en 50 instancias de $10 \times 10$.
- Ganador claro: CP-SAT (Constraint Programming + SAT). Fue el único en resolver el 100% de las instancias en menos de 180 segundos.
- Rendimiento a 1 segundo: CP-SAT resolvió 48/50, mientras que los otros resolvieron menos de la mitad.
Escalabilidad (Dataset de 700 instancias):
- Hasta $11 \times 11$: Tiempo medio de resolución < 1 segundo.
- Hasta $14 \times 14$: Tiempo medio < 5 segundos.
- Hasta $18 \times 18$: Tiempo medio < 1 minuto (48 segundos).
- Las instancias de $18 \times 18$ contenían aproximadamente 40,000 variables y 1 millón de restricciones lineales.

5. Contribuciones Clave y Significancia

Formalización Teórica: Es el primer trabajo que presenta un modelo ILP completo para el rompecabezas Evolomino, formalizando reglas complejas de evolución geométrica y conectividad.
Algoritmo de Generación: Introduce un método robusto para generar instancias de rompecabezas con solución única, un paso crítico para la creación de benchmarks y la validación de solucionadores.
Eficacia Práctica: Demuestra que, a pesar de la complejidad NP-completa del problema, los solucionadores modernos (específicamente CP-SAT) pueden manejar instancias de tamaño considerable ($18 \times 18$) en tiempos razonables, superando las limitaciones que tenían hace dos décadas.
Base para Futuras Investigaciones: Establece una base para explorar otros enfoques (como algoritmos DLX para cobertura exacta o programación por restricciones pura) y abre la puerta al estudio teórico de nuevos rompecabezas de lógica de papel.

En conclusión, el artículo valida que el enfoque de "transformar y conquistar" (traducir el rompecabezas a un problema de optimización matemática) es altamente efectivo para resolver y generar puzzles de lógica compleja como el Evolomino.