¶ Einleitung
Fillomino war zum ersten Mal in 1994 von Nikoli publiziert worden.- wikipedia Seite Nikoli
Fillomino ist ein logisches Zahlenpuzzle, das zur Familie der Rätselspiele gehört. In Nikoli-Magazinen wurde das Puzzle als „Fillomino“ bezeichnet. Der Name setzt sich zusammen aus "Fill" (englisch für „füllen“) und einer Anspielung auf „Polyomino“zusammen, eine geometrische Figur aus zusammenhängenden Quadraten.
Das gibt uns eine Vorstellung davon,was für ein spiel Fillomino ist.
¶ Regel
Die offizielle Regeln, die auf der Seite von Nikoli gefunden werden können lauten:
- Alle leeren Felder mit Zahlen gemäß den folgenden Regeln füllen.
- das gesamte Spielfeld in Blöcke aufteilen. jeden Block mit derselben Zahl, entweder horizontal oder vertikal füllen.
- Jeder Block enthält genau so viele Felder, wie die Zahl im Block angibt.
- Blöcke gleicher Größe dürfen sich weder horizontal noch vertikal berühren.
Blöcke sind auch Kacheln oder auf englisch "Polyominoes" genannt.
Zu Beginn erhalten wir ein Gitter mit einigen Hinweisen, die uns mithilfe der Regeln dabei helfen, das Puzzle zu lösen.
Für jedes Puzzle gibt es eine eindeutige Lösung.
FÜr diese Methode nehmen wir zusätzlich an, dass jede Kachel mindestens einen Vorgegebenen Wert enthält.
¶ Lösungsansatz
In dieser Wiki-Seite geht es hauptsächlich um den Lösungsansatz der Herren Pearce und Forbes.
Ihr Ansatz besteht darin, das Puzzle mithilfe von Lazy Constraints zu lösen.
Was soll man unter Lazy constraints verstehen?
¶ Lazy Constraints
Lazy Constraints sind eine Methode, die in der Optimierung und im Constraint Programming verwendet wird, um die Lösung eines Problems effizienter zu gestalten. Dabei werden im gegensatz eines normalen Constraint Programming Problem nicht alle Einschränkungen bzw. Nebenbedingungen (Constraints) sofort in das Optimierungsmodell integriert.
¶ Definition
Lazy Constraints werden nur dann hinzugefügt, wenn sie in einer Zwischenlösung verletzt werden. Das bedeutet, dass die Einschränkungen „faul“ sind, bis sie wirklich benötigt werden.
bei jeder Iterationen werden dann nicht immer alle Nebenbedingungen geprüft, sondern nur an bestimmte Zeit, wenn es benötigt wird. Diese sparrt uns dann Rechnerspeichert und Geschwindigkeit.
¶ Schritt für Schritt Funktionsweise
- Eine Lösung wird zunächst ohne bestimmte Constraints gesucht.
- Während des Lösungsprozesses prüft der Solver, ob eine gefundene Lösung gültig ist. (Bei dem Lösungsansatz wird das ein bisschen angepasst)
- Wenn die Lösung ungültig ist (weil sie eine Bedingung verletzt), wird die entsprechende Einschränkung hinzugefügt und der Lösungsprozess erneut ausgeführt.
¶ Vorteil
- Reduziert den Rechenaufwand.
- Besonders nützlich bei großen Modellen, in denen viele Constraints möglicherweise nie verletzt werden.
¶ Anwendung von lazy constraints
Die Lazy Constraints werden bei diesem Puzzle verwendet, um die Größe und die Formen der Kacheln zu kontrollieren. Es gibt über 10 wichtige Bedingungen; die ersten 6 werden vom Solver verarbeitet, bis eine potenzielle Lösung gefunden wird.
Anschließend wird diese potenzielle Lösung darauf geprüft, ob sie die ausgelassenen Nebenbedingungen erfüllt:
- Ja: Die nächste Nebenbedingung wird geprüft.
- Nein: Eine weitere Einschränkung wird dem Solver hinzugefügt, um erneut eine potenziell gültige Lösung zu finden und somit dann die Lösung zu verfeinern.
¶ Nutzung von Variablen
Beim Lazy-Constraints-Ansatz werden Variablen verwendet, um die Einträge in allen Zellen des Gitters zu repräsentieren. Das bedeutet, dass wir mithilfe von Variablen den Zustand und mindestens die Parameter (was eine Zelle sein kann und was nicht) bestimmen können.
Darüber hinaus liefern die Variablen auch die Anzahl der Kacheln jedes Typs und helfen bei der Festlegung von oberen und unteren Schranken für die Anzahl der Zellen jedes Typs.
Die Variablen erleichtern somit die Beschreibung des Spielzustands und die Lösung des Puzzles.
¶ Mengen, Daten, Variablen
Mengen:
- N, M: N Zeilen und M Spalten.
- K: Bereich der gültigen Zellwerte.
- Neighᵢⱼ: Nachbarn der Zelle (i, j). (kommt von englisch "neighbour")
Daten:
- Presetᵢⱼ: Vorgegebener Wert der Zelle (i, j). 0 bedeutet leer. ansonsten zwischen einschlißlich 1 bis je nachdem wie groß K ist.
Variablen:
- xᵢⱼₖ: 1, wenn die Zelle (i, j) den Wert k hat, sonst 0.
- yₖ: Anzahl der Kacheln des Typs k in dem gesamten Gitter.
¶ Die erste 6 Nebenbedingungen
¶ Nebenbedingung 1
Jede Zelle hat genau einen Wert:
Das bedeutet, dass die Summe von xijk an der Stelle (i, j) gleich 1 sein muss.
Das führt dazu, dass nur und wirklich nur für einen Wert von k xijk den Wert 1 haben kann.
Damit wird sichergestellt, dass jede Zelle nur einen einzigen Wert besitzt.
¶ Nebenbedingung 2
Dies bedeutet, dass die Regel für alle Werten von k gilt, außer für 0 und 1.
Presetij steht für die Hinweise, die wir bereits zu Beginn des Spiels zur Verfügung haben.
Diese Einschränkung deutet darauf hin, dass xijk nur für k = Presetij gleich 1 ist. Es legt dann die vorgegebene Werte fest.
¶ Nebenbedingung 3
Die Zahl k=1 ist nicht in der 2. enthalten, weil es ein bisschen besonders ist.
Für alle Zellen (i, j), deren vorgegebener Wert nicht 1 ist (Presetij 1), wird erzwungen, dass xij0 = 0. Mit anderen Worten:
Diese Zellen dürfen den Wert 1 nicht annehmen, da sie durch eine andere Vorgabe eingeschränkt sind.
Damit wird sichergestellt, dass der Solver nicht überall den Wert 1 einsetzen kann, was gemäß den bisher gegebenen Gesetzen theoretisch korrekt ist, jedoch die Annahme voraussetzt, dass jede Kachel mindestens einen vorgegebenen Wert enthält.
¶ Nebenbedingung 4
Diese Ungleichung stellt sicher, dass die Zelle (i, j) nur den Wert k annehmen kann, wenn einer ihrer Nachbarn den Wert k hat. Alle (a,b)-Nachbarn von (i,j) werden geprüft, und deren xabk-Wert wird aufsummiert. Das bedeutet, diese Summe wird nur 1 oder größer sein, wenn mindestens einer der Nachbarn den Wert k hat.
Damit wird sichergestellt, dass xijk 0 ist, wenn keiner der Nachbarn den Wert k hat. Folglich wird xijk= 0 (die Zelle (i, j) hat nicht den Wert k).
¶ Nebenbedingung 5
Wie in der Ungleichung zu sehen ist, gilt diese Bedingung besonders für k = 2.
Sie führt dazu, dass, wenn ein Hinweis den Wert 2 hat, nur ein Nachbar den Wert 2 annehmen kann. Mehr als ein Nachbar würde die Regel des Spiels verletzen.
Es wirkt anfangs kompliziert, aber diese Bedingung ist leicht zu verstehen, wenn man sie termweise betrachtet:
- Im Fall, dass (i, j) den Wert 2 hat, gilt (x_{ij2} = 1). Der letzte Term wird dadurch zu 0, und es bleibt nur:
Und hier sehen wir wieder den gleichen Gedankengang wie oben: Die Summe von (x_{ab2}) über alle Nachbarn ist 1, das heißt, nur ein Nachbar kann den Wert 1 annehmen.
- im Fall ,dass (i,j) 2, ist bekommen wir:
es ist wichtig zu betonen:
Diese Variable innerhalb der Betragszeichen repräsentiert die Anzahl der Elemente in der Menge.
Für eine Zelle in der Mitte eines Gitters ist 4, am Rand weniger.
Das erlaubt, dass die Summe von
bei maximal
liegt, wenn (i, j) selbst nicht den Wert 2 hat. Damit können die Nachbarn von (i,j) den Wert 2 haben.
Die Nachbarn von (i,j) können den Wert 2 annehmen, allerdings nur im Rahmen der Bedingung. Es wird sichergestellt, dass die Anzahl der Zellen mit 2 kontrolliert bleibt.
Diese Bedingung erlaubt es, dass Zellen mit 2 in einer zusammenhängenden Region gruppiert werden, ohne dass (i,j) selbst dazu gehört.
¶ Nebenbedingung 6
Diese Bedingung stellt sicher, dass die Summe der Variablen xijk über alle Zellen (i,j) für einen bestimmten wert k genau k * yk entspricht. Dabei repräsentiert yk die Anzahl der Kacheln mit dem Wert k, was sicherstellt, dass jede Region genau k Zellen enthält.
¶ Potenziell gültige Lösung gefunden
Nun hat der Solver eine potenziell gültige Lösung gefunden.
Was ist der nächste Schritt?
Wie bereits oben erwähnt, werden jetzt weitere Einschränkungen eingefügt, um die Lösung zu verfeinern.
Bei den nächsten zwei Nebenbedingungen geht es darum, die Größe der Kacheln zu kontrollieren.
Eine potenzielle Lösung könnte übergroße oder zu kleine Kacheln enthalten.
¶ Nebenbedingung 7
Diese Nebenbedingung bezieht sich auf übergroße Kacheln und dient als Einschränkung, um solche zu verhindern.
-
(T): Die Menge der Zellen, die zu einer übergroßen Kachel gehören.
-
Die Bedingung
stellt sicher, dass die Anzahl der Zellen xijk innerhalb der Kachel T kleiner als die Gesamtgröße T ist.
Damit wird verhindert, dass eine Kachel die maximal zulässige Größe überschreitet, indem sie übermäßig viele Zellen umfasst. Diese Einschränkung wurde auf Basis der vorherigen Regeln eingeführt, um die Konsistenz der Lösung zu wahren.
¶ Nebenbedingung 8
Begrenzung nach unten
Diese Nebenbedingung sorgt dafür, dass Kacheln korrekt eingegrenzt werden, indem sie die Summe von Zellen innerhalb und außerhalb der Kachel beschränkt. Die Bedingung lautet:
¶ die neue Variablen
-
T:
Die Menge der Zellen, die zu einer bestimmten Kachel gehören. Diese Kachel hat das Ziel, korrekt eingegrenzt zu werden. -
TN: Die Nachbarn der Kachel T, also alle Zellen, die direkt an die Kachel angrenzen. Diese Nachbarn helfen dabei, sicherzustellen, dass die Grenzen der Kachel eingehalten werden.
-
k*: Der Zielwert der Kachel. Das ist der Wert, den alle Zellen in der Kachel T teilen müssen. Zum Beispiel, wenn k*=3, bedeutet das, dass alle Zellen in T den Wert 3 haben.
-
k':
Alle Werte, die nicht gleich k* sind k' k*. Diese werden für die Nachbarzellen TN verwendet, um sicherzustellen, dass keine falschen Werte die Kachel überschreiten.
¶ Was macht die Nebenbedingung?
-
Erster Term:
Dieser Term zählt die Zellen in der Kachel T, die den Zielwert k* haben.
-
Zweiter Term:
Hier werden die Zellen in den Nachbarn TN überprüft, die einen anderen Wert k' als k* haben.
-
Gesamte Bedingung:
Die Bedingung stellt sicher, dass die Summe der Zellen in T und die falschen Werte der Nachbarn TN begrenzt bleibt. Dadurch wird verhindert, dass die Kachel über ihren Zielwert hinaus wächst oder falsche Werte erhält. Diese Bedingung stellt sicher, dass Kacheln die korrekte Größe und Form behalten.
Nachbarn, die nicht zum Zielwert gehören, dürfen die Grenzen der Kachel nicht verletzen.
¶ Anzahl der Zellen jedes Typs
Wie bereits früher erwähnt, dienen die Variablen auch dazu, die Anzahl der Zellen jedes Typs zu begrenzen. Dafür gibt es obere und untere Schranken. Welche Methoden dafür angewendet werden, wird in diesem Abschnitt besprochen:
¶ obere Schranke
Die Nebenbedingung 9
stellt sicher, dass die Anzahl der Kacheln vom Typ k, yk die maximale Anzahl verbundener Gruppen von Zellen des Typs k, Ck nicht überschreitet.
- Ck: Gibt die Anzahl der verbundenen Gruppen von Zellen für einen bestimmten Typ k an.
- Für k<3 gilt zusätzlich:
Das bedeutet, die Anzahl der Kacheln ist genau gleich der Anzahl der verbundenen Gruppen. Diese wird sicher gestellt dank Nebenbendingungen 5 und 3
¶ untere Schranke
Denn für k < 3haben wir eine Gleichung (yk = Ck ) betrachten wir hier k > 2.
für die Untere Schranken benutzen wir die sogennante Geodätische Distanz.
¶ Geodätische Distanz
Die geodätische Distanz im Kontext von Fillomino bezieht sich auf die minimale Anzahl von Schritten (Bewegungen von einer Zelle zur nächsten), die benötigt werden, um zwei Zellen innerhalb einer Kachel zu verbinden. Für die untere Schranke hilft sie sicherzustellen, dass die Anzahl der Zellen in einer Kachel mindestens der Summe der geodätischen Distanzen zwischen den Preset-Werten entspricht, um eine gültige Verbindung zu garantieren. Anders gesagt repräsentiert die Zahl, die Anzahl der Zellen, die hinzugefügt werden müssen, damit jede Zelle eine ZElle des Typs k wird.
Auf dieser Abbildung wird veranschaulicht, wie genau die geodätische Distanz funktioniert.
¶ Untere Schranke für 2 Hinweise in einer Kachel
Diese Regel legt fest, unter welchen Bedingungen zwei Hinweise Teil derselben Kachel sein können. Sie sorgt dafür, dass die Entfernung zwischen zwei Hinweisen die vorgegebenen Einschränkungen erfüllt.
- Zwei Hinweise können Teil einer Kachel sein.
- Die Bedingung lautet:
Distanz zwischen den beiden Hinweisen ist gültig, ansonsten wird die Zelle entfernt.
Diese Bedingung, obwohl sie nicht Teil der 10 Nebenbedingunen ist, wird auch als lazy constraints Dynamisch während der Laufzeit hinzugefügt, um die Lösung zu finden.
¶ Einschränkung der Position von Zellen
Es gibt ein paar Regeln die auch von dem Solver betrachtet werden sind. (ebenfalls dynamisch hinzugefügt)
- Nur Zellen mit zulässiger Distanz können Teil einer Kachel sein, das bedeutet (i,j) mit der Distanz > k von einem Hinweis des Typs k kann nicht Teil des durch den Hinweis erzeugten Kachels sein.
- wenn n Hinweise verbunden sind, können nur Zellen mit geodätischer Distanz k-n können Teil der Kachel sein.
- Alle Zellen, die nicht innerhalb der Distanz k-n liegen, werden ausgeschlossen: xijk=0.
¶ Nachbarn von Vorgaben
Nebenbedingung 10
Jede vorgegebene Gruppe von Zellen mit einer Distanzk-1 muss durch mindestens k Zellen desselben Typs abgedeckt werden. Dies wird durch die folgende Bedingung sichergestellt:
- (S): Die Menge aller Zellen, die eine Distanz von k-1 zur vorgegebenen Gruppe haben.
- Die Bedingung stellt sicher, dass die Gruppe S, die den Typ k repräsentiert, mindestens k Zellen umfasst.
- Diese Regel ist notwendig, um sicherzustellen, dass vorgegebene Gruppen mit ihrem Wert k vollständig und konsistent erweitert werden.
Diese Nebenbedingung spielt eine wichtige Rolle, um die Konsistenz der Lösung zu garantieren, indem alle Zellen innerhalb einer Kachel logisch miteinander verbunden bleiben.
¶ Zusammenfassung
- Lazy Constraints sind effektiv für Fillomino-Puzzles
- Dynamische Nebenbedingungen sparen Rechenzeit
- Geodätische Distanz und Vorverabeitung verbessern die Effizienz
Der Computer, den Pearce und Forbes für die Tests ihres Lösungsansatzes verwendet haben, wurde im Dokument nicht genauer beschrieben. Es wird lediglich angegeben, dass sie ihre Algorithmen mit Python 2.7 und dem Solver Gurobi 6.5 implementiert haben. Dies deutet darauf hin, dass die Hardware ausreichend war, um diese Tools effizient auszuführen, jedoch wurden keine genauen Spezifikationen wie CPU, RAM oder Betriebssystem genannt.
Diese Methode benötig zwischen 4 bis 26 Sekunden um eine Fillomino Puzzle zu lösen.
¶ Literatusverzeichnis
- Die offiziele Webseite von Nikoli über Fillomino: https://www.nikoli.co.jp/en/puzzles/fillomino/
- Die Wikipedia Seite über Fillomino:
https://de.wikipedia.org/wiki/Nikoli - Puzzle-The Fillomino Puzzle - Robin H. Pearce and Michael A. Forbes 2017:
https://publish.obsidian.md/mind-and-game/_papers/Puzzle—The+Fillomino+Puzzle+-+Pearce+and+Forbes+2017.pdf - "Integer Programming" von Laurence A. Wosley (1998)
ISBN: 978-0471283669 - "Constraint Logic Programkin using Eclipse" von Krysztof Apt und Mark Wallace (2007)