An Integer Linear Programming Model for the Evolomino Puzzle

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

Evolomino: Een Logisch Raadsel en de Wiskundige Sleutel

Stel je voor dat je een potlood en papier pakt om een raadsel op te lossen, net als een kruiswoordpuzzel, maar dan met blokjes. Dit raadsel heet Evolomino. Het is bedacht door het Japanse bedrijf Nikoli, dezelfde mensen die de wereldberoemde Sudoku hebben populair gemaakt.

In dit artikel vertellen twee Russische wiskundigen, Andrei en Yuri, hoe ze dit raadsel hebben "gekrakt" met behulp van geavanceerde computersoftware. Hier is de uitleg in simpele taal, met een paar grappige vergelijkingen.

1. Wat is het Evolomino-raadsel?

Stel je een rooster voor (zoals een schaakbord) met witte en grijze vakjes. Op sommige witte vakjes staan pijlen.

De taak: Je moet in de witte vakjes vierkantjes tekenen.
De regel: Deze vierkantjes vormen groepjes, die we "blokken" noemen.
De magie: Elke pijl leidt door een reeks van deze blokken. Het eerste blokje op de pijl is klein. Het volgende blokje op dezelfde pijl moet precies één vierkantje groter zijn dan het vorige, maar het mag niet draaien of spiegelen. Het is alsof een bloemknop langzaam openbloeit terwijl je de pijl volgt.
Het doel: Je moet zo tekenen dat alle regels kloppen en er maar één mogelijke oplossing is.

2. Het probleem: Waarom is dit moeilijk?

Voor een computer is dit raadsel als een enorme doolhof. Er zijn zoveel manieren om die blokjes te plaatsen dat het voor een simpele computer onmogelijk lijkt om de juiste weg te vinden zonder urenlang te zoeken. Wiskundig bewezen is dat dit een "NP-compleet" probleem is: dat is een fancy manier van zeggen dat het erg lastig is om te voorspellen of een oplossing bestaat, en dat het aantal mogelijke combinaties explosief groeit naarmate het bord groter wordt.

3. De oplossing: De "Recept-Boek" aanpak (ILP)

De auteurs hebben een manier bedacht om dit probleem te vertalen naar een taal die computers heel goed begrijpen: Integer Linear Programming (ILP).

Stel je voor dat je een kok bent die een heel complex gerecht moet koken. In plaats van te raden welke ingrediënten je moet gebruiken, schrijf je een strikt recept op:

"Als er een pijl is, moet er minstens één blokje zijn."
"Als blokje A er is, moet blokje B precies één stukje groter zijn."
"Blokjes mogen elkaar niet raken als ze van verschillende groepen zijn."

Deze regels vertalen ze naar een lange lijst met wiskundige vergelijkingen (zoals $x + y = 1$ ). Dit is het ILP-model. Het is alsof je de regels van het spel in een strakke, wiskundige "recept" giet.

4. De "Stroom" van de blokken (Connectiviteit)

Een van de lastigste regels is dat de blokjes aan elkaar moeten zitten (zoals een Lego-blokje dat niet uit elkaar valt).
De auteurs gebruiken hier een slimme truc die ze een "stroom" noemen.

Stel je voor dat het eerste blokje op de pijl een waterkraan is.
Dit water moet door alle andere blokjes van die groep stromen.
Als de groep uit elkaar valt (bijvoorbeeld twee losse blokjes die niet raken), kan het water niet bij het laatste blokje komen. De computer ziet dan: "Hé, de stroom is onderbroken! Dit is geen geldige oplossing."
Dit zorgt ervoor dat de computer alleen oplossingen accepteert waarbij de blokjes echt aan elkaar kleven.

5. Het Genereren van Nieuwe Puzzels

Niet alleen hebben ze een manier gevonden om het op te lossen, ze hebben ook een machine gebouwd om nieuwe puzzels te maken.

De computer begint met een leeg bord.
Hij tekent willekeurig pijlen en plaatst blokjes, net als een kind dat speelt met Lego.
Dan gebruikt hij zijn eigen "recept" (het ILP-model) om te controleren: "Heeft dit een unieke oplossing?"
Als er meerdere oplossingen zijn, haalt hij een stukje weg en probeert hij het opnieuw, tot hij een puzzel heeft die precies één oplossing heeft.
Dit is als een bakker die steeds nieuwe taarten bakt, maar elke keer eerst proeft of er precies één manier is om de taart te snijden.

6. De Resultaten: Hoe snel is het?

Ze hebben hun computer (met een moderne "CP-SAT" solver, een soort super-robot voor logica) laten werken op een reeks puzzels.

Kleine puzzels (11x11): De computer lost deze op in minder dan één seconde. Dat is sneller dan je kunt knipperen.
Grote puzzels (18x18): Zelfs deze enorme puzzels, met duizenden regels en variabelen, worden opgelost in minder dan één minuut.

Conclusie

Kortom: Dit artikel laat zien hoe je een leuk potlood-en-papier spelletje kunt vertalen naar een strikt wiskundig model. Door de regels van het spel om te zetten in een "recept" voor een computer, kunnen we deze puzzels niet alleen snel oplossen, maar ook automatisch nieuwe, unieke puzzels bedenken.

Het bewijst dat zelfs de meest ingewikkelde logica-puzzels, die eruitzien als een doolhof, opgelost kunnen worden als je ze maar in de juiste taal (wiskunde) vertaalt. De computer is hier de perfecte "detective" die geen enkele regel over het hoofd ziet.

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

Hier is een gedetailleerde technische samenvatting van het paper "An Integer Linear Programming Model for the Evolomino Puzzle" in het Nederlands.

Titel: Een Integer Lineair Programmeringsmodel voor de Evolomino-puzzel

Auteurs: Andrei V. Nikolaev en Yuri A. Myasnikov (P.G. Demidov Yaroslavl State University, Rusland)

1. Probleemdefinitie: Evolomino

Evolomino is een relatief nieuwe logische pen-en-papier puzzel, uitgegeven door het Japanse bedrijf Nikoli (bekend van Sudoku en Kakuro). De puzzel wordt gespeeld op een rechthoekig raster met witte en gearceerde cellen.

Doel: De speler moet vierkanten (□) tekenen in bepaalde witte cellen om "blokken" te vormen.
Regels:
1. Een blok is een groep verticaal of horizontaal verbonden vierkanten (een polyomino).
2. Elk blok moet precies één vierkant bevatten dat op een vooraf getekende pijl ligt.
3. Elke pijl moet door ten minste twee blokken lopen.
4. Evolutie: De blokken langs een pijl moeten "evolueren". Het tweede en daaropvolgende blok moet ontstaan door aan het vorige blok precies één vierkant toe te voegen, zonder rotatie of spiegeling.
Complexiteit: Het bepalen of een Evolomino-puzzel een oplossing heeft is NP-compleet, en het tellen van het aantal oplossingen is #P-compleet.

2. Methodologie

De auteurs vertalen de regels van Evolomino naar een Integer Linear Programming (ILP) model. Dit model maakt gebruik van lineaire constraints om de logica van de puzzel te coderen.

A. Variabelen

Het model introduceert drie hoofdtypen variabelen:

Cel-variabelen ( $x_i$ ): Geven aan of een cel een vierkant bevat (1) of niet (0).
Blok-variabelen ( $y_{i}^{a,k}$ ): Geven aan of cel $i$ behoort tot blok $k$ langs pijl $a$ .
Activeringsvariabelen ( $b_{a,k}$ ): Geven aan of blok $k$ langs pijl $a$ bestaat.
Stroom-variabelen ( $f_{ij}^{a,k}$ ): Gebruikt voor een flow-based model om de connectiviteit van polyomino's te garanderen (gebaseerd op het model van Gavish en Graves).
Translatie-variabelen ( $t_{j}^{a,k}$ ): Zorgen ervoor dat de vorm van het blok behouden blijft tijdens de evolutie (verschuiving zonder rotatie).

B. Constraints (Beperkingen)

De ILP-formulering omvat de volgende cruciale constraints:

Toewijzing: Elk vierkant behoort aan precies één blok.
Pijl-sequentie: Geen twee opeenvolgende cellen langs een pijl mogen beide vierkanten bevatten.
Blokgrootte: De grootte van blok $k$ moet exact één groter zijn dan blok $k-1$ (als beide bestaan).
Connectiviteit: Via een flow-model wordt gegarandeerd dat elk blok één samenhangend polyomino is. Er wordt een "bron" geplaatst op het vierkant dat op de pijl ligt; de stroom moet alle andere cellen van het blok bereiken.
Evolutie (Vormbehoud): De geometrische vorm van het blok moet behouden blijven bij de verschuiving naar het volgende blok. Dit wordt bereikt door te eisen dat als een cel in blok $k-1$ bestaat, het corresponderende verschoven punt in blok $k$ ook moet bestaan.

C. Puzzelgeneratie

De auteurs ontwikkelen een algoritme (Algorithm 1) om willekeurige Evolomino-puzzels te genereren met een unieke oplossing:

Opbouw: Start met een leeg raster en voeg pijlen toe via een "biased random walk" (voortbewegen is waarschijnlijker dan draaien).
Blokken plaatsen: Plaats blokken langs de pijlen met willekeurige evolutievormen.
Uniciteit garanderen: Na het plaatsen van alle elementen worden overgebleven lege cellen gearceerd. Vervolgens wordt een "greedy carving" toegepast: clues (pijlen en vooraf getekende vierkanten) worden willekeurig verwijderd. Als het verwijderen van een clue leidt tot meerdere oplossingen (gecontroleerd via de ILP-oplosser), wordt de clue teruggezet.

3. Belangrijkste Bijdragen

Formele ILP-modelleer: De eerste volledige vertaling van de Evolomino-regels naar een lineair programmeringsmodel, inclusief complexe constraints voor polyomino-connectiviteit en vormbehoud tijdens evolutie.
Schalingsanalyse: Een analyse van de grootte van het model. Het aantal variabelen is $O(K \cdot |C|)$ en het aantal constraints is $O(K \cdot |C|^2)$ , waarbij $K$ het aantal blokken en $|C|$ het aantal cellen is. De duurste constraints zijn die welke de geometrische consistentie tijdens evolutie garanderen.
Generatie-algoritme: Een robuust algoritme voor het genereren van unieke puzzelinstanties, essentieel voor het creëren van een benchmark-dataset.
Benchmark-dataset: Creatie van een dataset van 700 puzzels (500 met unieke oplossingen, 200 met gegarandeerde oplossingen) variërend van 5x5 tot 18x18.

4. Resultaten

De auteurs hebben het model getest met de CP-SAT-oplosser uit de Google OR-Tools bibliotheek (versie 9.15) op een Intel Core i7-13620H processor.

Vergelijking Oplossers: Op 10x10 instanties presteerde CP-SAT significant beter dan SCIP, CBC en BOP. CP-SAT loste 100% van de 50 testpuzzels op binnen 180 seconden, terwijl de anderen 94-96% haalden.
Schaalbaarheid:
- Tot 11x11: De mediane oplostijd is minder dan 1 seconde.
- Tot 14x14: De mediane oplostijd blijft onder de 5 seconden.
- Tot 18x18: De mediane oplostijd is 48 seconden (binnen de 1 minuut).
Modelgrootte: Voor een succesvol opgeloste 18x18 puzzel bevatte het model ongeveer 40.000 variabelen en 1 miljoen lineaire constraints.
Uitdagingen: Bij grotere maten (vanaf 15x15) neemt de variabiliteit in oplostijd toe (grotere IQR en outliers), wat wijst op minder homogene instanties en een minder voorspelbaar gedrag van de oplosser.

5. Betekenis en Conclusie

Dit paper toont aan dat moderne oplossers (zoals CP-SAT) zeer efficiënt zijn in het oplossen van complexe logische puzzels die als ILP-probleem kunnen worden geformuleerd, zelfs als het probleem theoretisch NP-compleet is.

Praktische toepasbaarheid: Hoewel de theoretische complexiteit hoog is, kunnen instanties tot 18x18 binnen een minuut worden opgelost, wat suggereert dat de structuur van de puzzel door de ILP-constraints goed wordt benut.
Toekomstig onderzoek: De auteurs suggereren alternatieve benaderingen zoals backtracking, SAT-modellen, of het reduceren tot het "exact cover"-probleem (DLX-algoritme) voor verdere optimalisatie.

Samenvattend biedt dit werk een solide wiskundige basis voor het oplossen en genereren van Evolomino-puzzels en demonstreert het de kracht van state-of-the-art solvers in de context van pen-en-papier logica.