An Integer Linear Programming Model for the Evolomino Puzzle

Questo articolo presenta un modello di programmazione lineare intera per formalizzare il puzzle logico Evolomino, introduce un algoritmo per generare istanze con soluzione unica e dimostra l'efficacia di un solver CP-SAT nel risolvere e creare puzzle fino a dimensioni di 18x18.

L'essenziale

Ecco una spiegazione semplice e creativa del paper, pensata per chiunque, anche senza conoscenze di matematica avanzata.

Immagina di trovarti davanti a un nuovo gioco da tavolo cartaceo, chiamato Evolomino. È come un incrocio tra un Sudoku e un gioco di costruzione con i mattoncini LEGO, ma con una regola magica: le forme che disegni devono "evolvere" mentre avanzi.

Gli autori di questo studio, due professori russi, hanno deciso di fare due cose fondamentali:

1. Capire come funziona il gioco trasformandolo in una serie di regole matematiche rigide (un modello di "Programmazione Lineare Intera").
2. Costruire un generatore automatico per creare nuovi livelli di questo gioco, assicurandosi che ogni livello abbia una sola soluzione possibile.

Ecco come hanno fatto, spiegato con metafore quotidiane:

1. Il Gioco: "L'evoluzione dei blocchi"

Immagina una griglia bianca e grigia. Ci sono delle frecce disegnate su alcuni quadrati bianchi.

• La regola: Devi disegnare dei quadrati (□) su alcuni spazi bianchi.
• Il blocco: I quadrati che tocchi tra loro formano un "blocco" (come un pezzo di Tetris).
• L'evoluzione: Ogni freccia deve attraversare almeno due blocchi. Il primo blocco è piccolo. Il secondo blocco deve essere esattamente uguale al primo, ma più grande di un solo quadrato, e non deve essere ruotato o girato. Deve solo "scivolare" in avanti lungo la freccia.
• Il problema: Trovare dove mettere i quadrati è difficile perché ci sono migliaia di combinazioni possibili. È come cercare di indovinare la combinazione di una cassaforte con milioni di numeri.

2. La Soluzione Matematica: "Il traduttore per i computer"

Gli autori hanno detto: "Non possiamo risolvere questo puzzle a mano per ogni livello, ma possiamo insegnarlo a un computer".
Hanno creato un traduttore (il modello ILP).

• Immagina di dare al computer un foglio di calcolo gigante.
• Ogni cella del gioco diventa una domanda: "C'è un quadrato qui? Sì (1) o No (0)?".
• Poi hanno scritto delle regole matematiche (equazioni) che dicono al computer: "Se c'è un quadrato qui, non può essercene un altro qui sotto", oppure "Se questo blocco è grande 2, il prossimo deve essere grande 3".
• È come dare al computer un manuale di istruzioni così preciso che non può sbagliare. Se le regole sono rispettate, il puzzle è risolto.

3. Il Generatore di Livelli: "L'architetto che costruisce e poi smonta"

Creare un puzzle è facile (disegni a caso e vedi se funziona). Creare un puzzle perfetto (che abbia una sola soluzione e non sia troppo facile né troppo difficile) è durissimo.
Gli autori hanno inventato un algoritmo che funziona come un architetto che costruisce una casa e poi la smonta:

1. Costruzione: Il computer disegna frecce e blocchi a caso su una griglia vuota, seguendo le regole di evoluzione.
2. Verifica: Controlla se c'è una sola soluzione.
3. Smontaggio (Il trucco): Una volta trovato un puzzle valido, il computer inizia a togliere i "indizi" (i quadrati già disegnati e le frecce) uno per uno.
   • Togli un indizio: "Ok, c'è ancora una sola soluzione? Sì. Lascialo fuori."
   • Togli un altro indizio: "Aspetta, ora ci sono due soluzioni possibili! Rimettilo."
4. Risultato: Alla fine, ottieni un puzzle con il numero minimo di indizi necessari per essere risolto in un solo modo. È come scolpire una statua: togli la pietra in eccesso finché non rimane solo la forma perfetta.

4. I Risultati: "Il super-computer che corre"

Hanno testato il loro sistema su un computer normale (un portatile moderno).

• Piccoli livelli (5x5 fino a 11x11): Il computer li risolve in meno di un secondo. È come se risolvesse un Sudoku in un battito di ciglia.
• Livelli grandi (fino a 18x18): Ci vogliono circa un minuto.
• Il vincitore: Tra i vari "motori" di calcolo che hanno provato, uno chiamato CP-SAT (un po' come un super-istruttore che sa combinare logica e ricerca) è stato il migliore, risolvendo tutto velocemente.

In sintesi

Questo paper è come un manuale di istruzioni per insegnare a un computer a giocare e a creare il gioco "Evolomino".

• Hanno tradotto le regole del gioco in matematica.
• Hanno creato un robot che genera nuovi livelli perfetti.
• Hanno dimostrato che, anche se il gioco sembra complicato, con gli strumenti giusti (i moderni solutori matematici) si può risolvere e creare in tempi record.

È un esempio bellissimo di come la matematica possa trasformare un passatempo di carta e matita in un problema risolvibile con la potenza di calcolo moderna, rendendo possibile creare infinite nuove sfide per i giocatori.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "An Integer Linear Programming Model for the Evolomino Puzzle", presentata in italiano.

1. Il Problema: Evolomino

L'Evolomino è un nuovo puzzle logico "penna e carta" pubblicato dalla casa editrice giapponese Nikoli (nota per Sudoku e Kakuro), apparso per la prima volta nel marzo 2023.

• Meccanica: Il gioco si svolge su una griglia rettangolare contenente celle bianche e ombreggiate. Alcune celle bianche contengono frecce pre-stampate.
• Obiettivo: Il giocatore deve disegnare quadrati (□) in alcune celle bianche per formare dei "blocchi" (poliomini).
• Regole Chiave:
  1. Ogni blocco deve contenere esattamente un quadrato posizionato su una freccia pre-stampata.
  2. Ogni freccia deve attraversare almeno due blocchi.
  3. Evoluzione: I blocchi successivi lungo il percorso di una freccia devono "evolvere" aggiungendo esattamente un quadrato al blocco precedente, senza rotazione o riflessione.
  4. I blocchi devono essere connessi (poliomini connessi).
• Complessità Computazionale: È stato dimostrato che decidere se un'istanza di Evolomino ha una soluzione valida è un problema NP-completo (riduzione da 3-SAT) e che il problema di contare le soluzioni distinte è #P-completo.

2. Metodologia: Modello di Programmazione Lineare Intera (ILP)

Gli autori formalizzano le regole del puzzle come un modello di Programmazione Lineare Intera (ILP), utilizzando vincoli lineari per codificare l'evoluzione dei blocchi, la connettività e la coerenza.

Variabili Decisionali

• $x_i$: Variabile binaria per ogni cella $i$ (1 se contiene un quadrato, 0 altrimenti).
• $y_{a,i}^k$: Variabile binaria che indica se la cella $i$ appartiene al $k$-esimo blocco lungo la freccia $a$.
• $b_a^k$: Variabile di attivazione (1 se il $k$-esimo blocco sulla freccia $a$ esiste).
• $N_a^k$: Variabile intera che rappresenta la dimensione (numero di quadrati) del $k$-esimo blocco.
• $F_{a,i}^k$: Variabile di flusso che indica se la cella $i$ è la "sorgente" del blocco $k$ sulla freccia $a$.
• $f_{a,ij}^k$: Variabili di flusso intero per garantire la connettività del poliomino.
• $t_{a,j}^k$: Variabile binaria che indica la traslazione (shift) applicata per passare dal blocco $k-1$ al blocco $k$.

Vincoli Principali

1. Assegnazione e Attivazione: Ogni quadrato appartiene a un solo blocco; i blocchi non attivati sono vuoti; i blocchi attivati contengono esattamente un quadrato sulla freccia.
2. Evoluzione Geometrica:
   • La dimensione del blocco $k$ deve essere esattamente quella del blocco $k-1$ più uno ($N_a^k = N_a^{k-1} + 1$).
   • Vincoli di Corrispondenza: Se un quadrato è presente nel blocco $k-1$ in una certa posizione, deve essere presente nel blocco $k$ nella posizione traslata corrispondente. Questo vincolo (eq. 21) è cruciale per preservare la forma senza rotazioni.
3. Connettività (Flusso): Utilizzando un modello di flusso basato su Gavish e Graves, gli autori garantiscono che ogni blocco formi un unico poliomino connesso. Una sorgente (il quadrato sulla freccia) genera un flusso pari alla dimensione del blocco, che deve raggiungere tutte le altre celle del blocco.
4. Consistenza: Due celle adiacenti non possono appartenere a blocchi diversi (per evitare sovrapposizioni o frammentazioni non valide).

3. Contributi Chiave

1. Formalizzazione ILP: Prima modellazione matematica completa delle regole di Evolomino, permettendo l'uso di solver moderni per la risoluzione.
2. Algoritmo di Generazione: Sviluppo di un algoritmo (Algorithm 1) per generare istanze casuali di Evolomino con soluzione unica.
   • L'algoritmo utilizza una passeggiata casuale (biased random walk) per disegnare le frecce.
   • Posiziona i blocchi in modo ricorsivo.
   • Utilizza un processo di "scavo" (carving) greedy: rimuove casualmente indizi (quadrati o celle ombreggiate) e verifica con il solver ILP se la soluzione rimane unica. Se una rimozione crea soluzioni multiple, l'indizio viene ripristinato.
3. Analisi della Complessità: Stima della crescita del modello. Il numero di variabili è $O(K \cdot |C|)$ e il numero di vincoli è dominato da $O(K \cdot |C|^2)$, dove $K$ è il numero di blocchi e $|C|$ il numero di celle.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su un dataset personalizzato (700 istanze) utilizzando il solver CP-SAT di Google OR-Tools, confrontato con SCIP, CBC e BOP.

• Confronto Solver: Su istanze 10x10, CP-SAT si è dimostrato nettamente superiore, risolvendo il 100% delle istanze entro 180 secondi, mentre gli altri solver ne risolvevano circa il 94%.
• Scalabilità:
  • 11x11: Tempo mediano di risoluzione < 1 secondo.
  • 14x14: Tempo mediano < 5 secondi.
  • 15x15 - 18x18: Il tempo di esecuzione cresce esponenzialmente. Per le istanze 18x18, il tempo mediano è di circa 48 secondi (sotto il minuto), con un modello contenente circa 40.000 variabili e 1 milione di vincoli lineari.
• Efficienza: Nonostante la complessità teorica (NP-completo), i solver moderni gestiscono istanze di dimensioni significative in tempi pratici grazie ai miglioramenti algoritmici e hardware degli ultimi decenni.

5. Significato e Conclusioni

Questo lavoro è significativo perché:

• Porta un nuovo puzzle logico nel dominio della ricerca operativa e dell'informatica teorica.
• Dimostra che problemi di puzzle complessi, anche se NP-completi, possono essere risolti efficientemente in pratica tramite modelli ILP e solver CP-SAT avanzati.
• Fornisce un framework generativo robusto per creare nuovi puzzle con garanzie matematiche di unicità della soluzione.
• Apre la strada a futuri studi che potrebbero esplorare approcci alternativi come backtracking, programmazione per vincoli (CP) pura, o algoritmi basati su "Dancing Links" (DLX) per il problema della copertura esatta.

In sintesi, gli autori hanno trasformato un enigma logico recente in un problema di ottimizzazione risolvibile, fornendo sia la teoria matematica che gli strumenti pratici per la sua analisi e generazione.