An Integer Linear Programming Model for the Evolomino Puzzle

Diese Arbeit stellt ein ganzzahliges lineares Optimierungsmodell zur formalen Beschreibung des Logikrätsels Evolomino vor, das zur Generierung eindeutiger Rätselinstanzen genutzt wird und durch Experimente zeigt, dass ein moderner CP-SAT-Löser bis zu 18×18 große Gitter effizient bewältigen kann.

Das Wesentliche

Stellen Sie sich vor, Sie sitzen an einem Schreibtisch und haben ein neues, faszinierendes Logikrätsel vor sich, das von den japanischen Meistern des „Nikoli"-Verlags erfunden wurde. Es heißt Evolomino.

Statt nur Zahlen in Kästchen zu schreiben (wie bei Sudoku), müssen Sie hier kleine Quadrate zeichnen, die sich wie lebendige Organismen verhalten. Aber keine Sorge, in diesem Artikel erklären wir nicht nur das Rätsel, sondern auch, wie die Autoren – zwei Mathematiker aus Russland – es in die Sprache eines Computer-Programmierers übersetzt haben, damit ein Computer es lösen kann.

Hier ist die Geschichte des Papiers, einfach erklärt:

1. Das Rätsel: Ein Puzzle, das wächst

Stellen Sie sich ein Schachbrett vor, auf dem einige Felder grau (verboten) und andere weiß (begehbar) sind. Auf einigen weißen Feldern stehen kleine Pfeile.

• Die Aufgabe: Sie müssen in die weißen Felder Quadrate (□) setzen.
• Die Magie: Diese Quadrate bilden Gruppen, die wir „Blöcke" nennen. Jeder Block muss mindestens ein Quadrat enthalten, das auf einem Pfeil liegt.
• Die Evolution: Das ist der spannende Teil. Ein Pfeil zeigt eine Richtung. Entlang dieses Pfeils müssen die Blöcke „wachsen".
  • Der erste Block ist klein.
  • Der zweite Block muss genau ein Quadrat größer sein als der erste.
  • Der dritte muss wieder eins größer sein als der zweite.
  • Wichtig: Sie dürfen die Form nicht drehen oder spiegeln. Es ist, als würde ein Schneemann wachsen, indem er einfach nur einen neuen Schneeball oben draufsetzt, ohne den ganzen Körper neu zu formen.

Das Ziel ist es, das ganze Brett so zu füllen, dass alle Pfeile ihre Regeln befolgen und keine zwei Blöcke sich gegenseitig stören.

2. Die Herausforderung: Warum Computer das schwer finden

Das klingt einfach, aber für einen Computer ist das ein Albtraum. Stellen Sie sich vor, Sie müssten in einem riesigen Labyrinth alle möglichen Wege ausprobieren, um zu sehen, welcher Weg funktioniert. Bei einem 10x10-Brett gibt es so viele Möglichkeiten, dass es länger dauert als das Alter des Universums, sie alle einzeln durchzuprobieren.

Bisher gab es nur einen Beweis, dass dieses Rätsel extrem schwierig ist (mathematisch gesehen „NP-vollständig"). Das bedeutet: Es gibt keinen schnellen, einfachen Trick, um es immer sofort zu lösen.

3. Die Lösung: Die Übersetzung in eine „Rezeptur"

Die Autoren des Papiers haben eine clevere Idee gehabt. Statt dem Computer zu sagen: „Versuch mal, das Rätsel zu lösen!", haben sie ihm eine Rezeptur gegeben.

Sie haben die Regeln des Puzzles in eine Sprache übersetzt, die Computer lieben: Ganze Zahlen und lineare Gleichungen (Integer Linear Programming).

Stellen Sie sich das wie einen sehr strengen Koch vor, der ein Rezept für einen Kuchen hat:

• „Wenn du Mehl (ein Quadrat) in Schale A (Zelle 1) tust, darfst du in Schale B (Zelle 2) kein Mehl haben."
• „Wenn der erste Teigling (Block 1) 3 Stück groß ist, muss der zweite Teigling (Block 2) genau 4 Stück groß sein."
• „Alle Teiglinge müssen aneinander kleben, wie ein einziger Knetkloß."

Der Computer nimmt dieses Rezept und rechnet blitzschnell aus, welche Kombination von „Mehl" und „Zucker" (Quadraten) alle Regeln gleichzeitig erfüllt.

4. Der neue Generator: Ein Puzzle-Designer mit Magie

Nicht nur das Lösen war das Ziel. Die Autoren wollten auch neue Rätsel erfinden. Aber wie erstellt man ein Rätsel, das genau eine Lösung hat?

Sie haben einen Algorithmus (eine Art digitaler Puzzle-Architekt) gebaut:

1. Er fängt mit einem leeren Brett an.
2. Er zeichnet zufällig Pfeile.
3. Er baut die wachsenden Blöcke darauf.
4. Der Clou: Am Ende schaut er sich das fertige Bild an und fängt an, Teile davon wegzunehmen (wie ein Bildhauer, der Stein wegschlägt). Er nimmt ein Quadrat weg, prüft: „Hat das Rätsel jetzt noch nur eine Lösung?" Wenn ja, bleibt es weg. Wenn nein (es gäbe zwei Lösungen), setzt er es wieder zurück.

So entsteht ein perfektes Rätsel, das genau eine Lösung hat, aber schwer zu knacken ist.

5. Das Ergebnis: Ein Rennwagen im Logik-Dschungel

Die Autoren haben ihren Computer-Code (einen sogenannten „CP-SAT Solver") getestet. Das Ergebnis war beeindruckend:

• Bei kleinen Rätseln (5x5 bis 11x11) war der Computer schneller als ein Blinzeln (unter einer Sekunde).
• Selbst bei großen Rätseln (18x18, also 324 Felder) brauchte er nur etwa eine Minute.

Das ist wie ein Rennwagen, der durch einen dichten Wald fährt, während andere Autos (ältere Methoden) noch im Dschungel stecken bleiben.

Fazit

Dieses Papier ist wie eine Brücke zwischen zwei Welten:

1. Die Welt der Spaß-Rätsel, die man am Kaffeehaustisch löst.
2. Die Welt der harten Mathematik, die komplexe Probleme in einfache Gleichungen zerlegt.

Die Autoren haben gezeigt, dass man auch für sehr neue und knifflige Rätsel wie Evolomino eine mathematische „Rezeptur" finden kann, mit der moderne Computer in Sekundenbruchteilen Meisterleistungen vollbringen. Und sie haben uns einen Werkzeugkasten gegeben, um unendlich viele neue, spannende Rätsel für uns alle zu erfinden.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „An Integer Linear Programming Model for the Evolomino Puzzle" auf Deutsch:

1. Problemstellung: Evolomino

Das Paper beschäftigt sich mit Evolomino, einem neuen Logikrätsel vom Typ „Stift und Papier", das von der japanischen Firma Nikoli (bekannt für Sudoku, Kakuro, Slitherlink) im März 2023 veröffentlicht wurde.

• Spielmechanik: Das Spiel findet auf einem rechteckigen Gitter mit weißen und schattierten Zellen statt. Einige weiße Zellen enthalten vordefinierte Quadrate und Pfeile.
• Ziel: Der Spieler muss in einigen weißen Zellen Quadrate zeichnen, um „Blöcke" (Polyomino-ähnliche Gruppen von Quadraten) zu bilden.
• Regeln:
  1. Jeder Block muss genau ein Quadrat enthalten, das auf einem vordefinierten Pfeil liegt.
  2. Jeder Pfeil muss mindestens zwei Blöcke durchlaufen.
  3. Evolution: Die Blöcke entlang eines Pfeils müssen sich „entwickeln". Der zweite und folgende Blöcke entstehen, indem dem vorherigen Block genau ein Quadrat hinzugefügt wird, ohne Rotation oder Spiegelung. Die Form muss also durch reine Translation (Verschiebung) erhalten bleiben.
  4. Die Blöcke müssen zusammenhängend (verbunden) sein.

Bisher gab es nur theoretische Komplexitätsanalysen (NP-vollständig für die Existenz einer Lösung, #P-vollständig für das Zählen der Lösungen), aber keine effizienten Algorithmen zur Lösung oder Generierung.

2. Methodik: Integer Linear Programming (ILP) Modell

Die Autoren formulieren die Regeln von Evolomino als ganzzahliges lineares Programm (ILP). Das Modell nutzt moderne Solver, um die kombinatorischen Constraints zu lösen.

Variablen

• Zellvariablen ($x_i$): Binärvariable, ob eine Zelle ein Quadrat enthält.
• Blockvariablen ($y_{a,i}^k$): Binärvariable, ob Zelle $i$ zum $k$-ten Block auf Pfeil $a$ gehört.
• Aktivierungsvariablen ($b_a^k$): Gibt an, ob der $k$-te Block auf Pfeil $a$ existiert.
• Flussvariablen ($f_{ij}^{ak}$): Ganzzahlige Variablen zur Sicherstellung der Zusammenhangskomponente (Connectivity) jedes Blocks, basierend auf einem Fluss-Modell (Gavish & Graves).
• Translationsvariablen ($t_{j}^{ak}$): Binärvariable, die die Verschiebung (Shift) zwischen Block $k-1$ und Block $k$ kodiert.

Wichtige Constraints

1. Zuordnung: Jedes Quadrat gehört genau einem Block.
2. Keine Nachbarschaft: Auf einem Pfeil dürfen keine zwei aufeinanderfolgenden Zellen beide Quadrate enthalten (Lücke erforderlich).
3. Blockgröße und Evolution:
   • Die Größe des $k$-ten Blocks muss genau um 1 größer sein als die des $(k-1)$-ten Blocks.
   • Geometrische Konsistenz: Ein Quadrat in Block $k-1$ an Position $i$ muss in Block $k$ an Position $i+j$ erscheinen, wobei $j$ eine erlaubte Translation ist. Dies wird durch lineare Ungleichungen erzwungen, die Rotation und Spiegelung ausschließen.
4. Konnektivität (Flow): Ein Fluss wird von der „Quellzelle" (dem Quadrat auf dem Pfeil) erzeugt und muss alle anderen Zellen des Blocks erreichen. Dies garantiert, dass der Block ein zusammenhängendes Polyomino ist.

Skalierung des Modells

Die Anzahl der Variablen skaliert mit $O(K \cdot |C|)$ (wobei $K$ die maximale Anzahl an Blöcken und $|C|$ die Zellenanzahl ist). Die Anzahl der Constraints skaliert mit $O(K \cdot |C|^2)$, wobei die teuersten Constraints die geometrische Konsistenz während der Evolution sicherstellen.

3. Puzzle-Generierung

Die Autoren entwickelten einen Algorithmus (Algorithmus 1), um zufällige Evolomino-Rätsel mit eindeutiger Lösung zu generieren:

1. Aufbau: Startend mit einem leeren Gitter werden Pfeile durch einen verzerrten Random Walk (bevorzugt gerade Linie) platziert.
2. Block-Platzierung: Für jeden Pfeil werden Blöcke rekursiv platziert, wobei die Evolution (Hinzufügen eines Quadrats) und Kollisionsvermeidung geprüft werden.
3. Verfeinerung (Carving): Nach dem Platzieren aller Hinweise werden überflüssige Zellen (leere oder schattierte) entfernt.
4. Eindeutigkeitsprüfung: Bei jedem Entfernen wird das ILP-Modell aufgerufen, um sicherzustellen, dass keine alternative Lösung existiert. Falls ja, wird die Änderung rückgängig gemacht.
   • Hinweis: Für sehr große Instanzen (ab 15x15) wurde dieser Schritt vereinfacht, da die wiederholten Solver-Aufrufe zu rechenintensiv wurden.

4. Ergebnisse und Experimente

Die Experimente wurden mit dem CP-SAT Solver aus der Google OR-Tools Bibliothek durchgeführt (verglichen mit SCIP, CBC und BOP).

• Solver-Vergleich: CP-SAT erwies sich als eindeutig überlegen. Bei 50 Instanzen der Größe 10x10 löste CP-SAT alle innerhalb von 180 Sekunden, während andere Solver einige Instanzen verfehlten.
• Leistung nach Größe:
  • Bis 11x11: Median-Lösungszeit unter 1 Sekunde.
  • Bis 14x14: Median-Lösungszeit unter 5 Sekunden.
  • Bis 18x18: Median-Lösungszeit unter 1 Minute (ca. 48 Sekunden).
• Komplexität: Selbst für die 18x18-Instanzen, die etwa 40.000 Variablen und eine Million lineare Constraints enthielten, war das Modell lösbar.
• Skalierung: Die Lösungszeit wächst exponentiell mit der Gittergröße, was durch die kubische Zunahme der Constraints ($O(K \cdot |C|^2)$) bedingt ist. Dennoch zeigt sich, dass moderne Solver in der Lage sind, diese NP-vollständigen Probleme für praktische Größenordnungen effizient zu bewältigen.

5. Bedeutung und Fazit

• Theoretischer Beitrag: Das Paper liefert das erste formale ILP-Modell für Evolomino und erweitert die Methodik zur Lösung von Nikoli-Rätseln.
• Praktische Anwendung: Es wird ein vollständiger Generator für Rätsel mit garantierter Eindeutigkeit bereitgestellt, der als Benchmark-Dataset für zukünftige Forschung dient.
• Effizienz: Die Ergebnisse demonstrieren, dass selbst komplexe, evolutionäre Polyomino-Probleme mit modernen Constraint-Programming-Techniken (CP-SAT) effizient gelöst werden können, obwohl das Problem theoretisch NP-vollständig ist.
• Zukunftsausblick: Die Autoren schlagen alternative Ansätze wie Backtracking, SAT-basierte Modelle oder den DLX-Algorithmus (Dancing Links) für die Lösung und Generierung als weitere Forschungsrichtungen vor.

Zusammenfassend beweist das Paper, dass Evolomino nicht nur ein unterhaltsames Rätsel, sondern auch ein interessantes Testfeld für kombinatorische Optimierungsalgorithmen ist, das mit aktuellen ILP-Techniken effektiv handhabbar ist.