¶ Einführung
Numberlink, auch unter dem Namen Arukone bekannt, ist ein spannendes und herausforderndes Logikrätsel, das weltweit von Rätselenthusiasten geschätzt wird. Ziel des Spiels ist es, Paare von gleich nummerierten Punkten auf einem Gitter zu verbinden. Dabei müssen die Verbindungen durchgehende Linien bilden, ohne sich zu überschneiden oder zu kreuzen. Die Herausforderung besteht darin, alle Punkte miteinander zu verbinden, während du gleichzeitig sicherstellst, dass keine der Linien den vorgegebenen Regeln widerspricht.
¶ Geschichte[1]
Numberlink, ursprünglich in einer leicht abgewandelten Form von Sam Loyd im Jahr 1897 in der Brooklyn Daily Eagle veröffentlicht, fand später in Henry Ernest Dudeneys Buch Amusements in Mathematics (1917) als "Puzzle für Autofahrer" bekannt.
In Japan wurde das Spiel von der Rätselgesellschaft Nikoli unter den Namen Arukone (mit Buchstabenpaaren) und Nanbarinku (mit Zahlenpaaren) populär. Seit 2006 hat Nikoli mehrere Bücher mit Numberlink-Rätseln veröffentlicht, was zur internationalen Verbreitung des Spiels beigetragen hat.
¶ Regeln[1:1][2]
Die Regeln für Numberlink sind einfach, aber die Lösung eines Rätsels kann viel Denkarbeit erfordern. Hier sind die grundlegenden Regeln:
-
Verbindung der Paare: Jedes Paar von gleich nummerierten Punkten muss mit einer Linie verbunden werden. Diese Linien können nur horizontal oder vertikal verlaufen.
-
Durchgehende Linien: Jede Verbindung muss eine durchgehende Linie sein, die von einem Punkt zu seinem entsprechenden Partner führt. Die Linien dürfen nicht unterbrochen oder in mehrere Teile aufgeteilt werden.
-
Keine Überschneidungen: Die Linien der verschiedenen Paare dürfen sich nicht überschneiden oder kreuzen. Dies bedeutet, dass der Pfad eines Paares niemals den Pfad eines anderen Paars schneiden darf.
-
Abdeckung aller Felder: Alle Felder auf dem Gitter müssen durch eine der Linien abgedeckt sein. Das bedeutet, dass jeder leere Raum durch die Verbindungen genutzt werden muss, um das Gitter vollständig zu füllen.
-
Keine Diagonalen: Die Linien dürfen ausschließlich horizontal oder vertikal verlaufen, nicht diagonal.
-
Einzigartige Lösung: Jedes Numberlink-Rätsel hat eine eindeutige Lösung, die alle Bedingungen erfüllt, wenn es korrekt gelöst wird.
¶ Ansatz zur Lösung von Numberlink nach Knuth
Der Ansatz kombiniert die Prinzipien von Knuths SIMPATH-Algorithmus[3] mit den spezifischen Anforderungen des Numberlink-Problems, um eine effiziente und systematische Lösungsmethode bereitzustellen. Knuths Algorithmus basiert auf der Konstruktion von Zero-Suppressed Binary Decision Diagrams (ZDDs), die sämtliche s-t-Pfade[2:1] in einem Graphen darstellen. Für das Numberlink-Problem wird dieser Algorithmus so erweitert, dass alle gültigen Pfadkombinationen erfasst werden, die den spezifischen Anforderungen der Aufgabe entsprechen.
Hinweis: Bitte lesen Sie den ZDD-Wiki-Artikel für ein besseres Verständnis
¶ Eingabe
Die Eingabe für den Algorithmus besteht aus den folgenden Elementen:
¶ 1. Graph
- Der Graph stellt das Gitter des Numberlink-Problems dar.
- Die Knoten repräsentieren die Zellen im Gitter, während die Kanten die möglichen Verbindungen zwischen benachbarten Zellen darstellen.
¶ 2. Menge
Info:
Die Menge gibt die Paare von Knoten an, die miteinander verbunden werden müssen.
Jedes Element in ist ein Paar , wobei und die Start- und Zielknoten eines Pfads sind.
¶ Ziel
Info:
Das Ziel des Numberlink-Problems ist es, alle gültige Lösung zu finden
¶ Einschränkungen[2:2]
Während des Algorithmus wird vor jeder Entscheidung geprüft, ob der aktuelle Zustand des Pfads kompatibel mit den Anforderungen ist. Inkompatible Zustände werden frühzeitig verworfen.
| Bedingung | Beschreibung |
|---|---|
| E(π) ist eine gültige Pfadabgleichung (Path Matching) | Ein Pfad ist nur dann gültig, wenn er eine korrekte Pfadabgleichung bildet. |
| Knoten mit Grad 2 in | Kein Knoten darf gleichzeitig an zwei verschiedenen Pfaden beteiligt sein. |
| Knoten mit Grad 0 in | Jeder Knoten in muss Teil eines gültigen Pfads sein. |
| Inkompatible Knotenpaare | Es dürfen keine Verbindungen zwischen Knotenpaaren existieren, die nicht in definiert sind. |
| Knoten außerhalb von mit Grad 1 in | Kein Knoten außerhalb von darf isoliert oder nur Teil eines unvollständigen Pfads sein. |
Info: Diese Einschränkungen sind entscheidend, um sicherzustellen, dass die erzeugten Pfade kompatibel mit den Vorgaben sind. Verstöße führen zur frühzeitigen Verwerfung der entsprechenden Zustände[2:3].
¶ Definition von [2:4]
Ein Pfad in einer ZDD ist gültig, wenn er in einem Terminalknoten endet. Die Menge umfasst alle Kanten , die durch 1-Kanten im Pfad ausgewählt wurden:
„“.
Kurz: ist die Menge der Kanten, die im Pfad enthalten sind.
¶ Algorithmus zur Lösung des Numberlink-Problems
Der Algorithmus arbeitet wie folgt:
-
Initialisierung:
- Erstelle einen Wurzelknoten (Startzustand) und zwei Endknoten ( und ):
- : repräsentiert inkonsistente Pfade.
- : repräsentiert gültige Lösungen.
- Initialisiere eine leere Zustandsmenge für jeden Schritt der Verarbeitung.
- Erstelle einen Wurzelknoten (Startzustand) und zwei Endknoten ( und ):
-
Iterative Verarbeitung der Kanten:
- Jede Kante im Graphen wird nacheinander betrachtet.
- Für jede Kante wird entschieden:
- Zustand 1: Kante wird in den Pfad aufgenommen.
- Zustand 0: Kante wird nicht aufgenommen.
-
Kompatibilitätsprüfung:
- Vor Aufnahme einer Kante wird geprüft, ob der aktuelle Zustand mit den Einschränkungen kompatibel ist:
- Inkompatible Zustände: Verwerfen (Kind-Knoten wird auf gesetzt).
- Kompatible Zustände: Weiterverarbeitung mit der Mate-Funktion.
- Vor Aufnahme einer Kante wird geprüft, ob der aktuelle Zustand mit den Einschränkungen kompatibel ist:
-
Diagrammkonstruktion:
- Verarbeite alle Kanten, um ein vollständiges ZDD zu erstellen.
- Das ZDD repräsentiert alle gültigen Lösungen des Problems.
¶ Pseudocode des erweiterten Algorithmus[2:5]
Beginne:
Erstelle einen Wurzelknoten und zwei Endknoten 0 und 1;
Setze N1 ← {n_root} und Ni ← ∅ für i = 2, . . . , |E|;
Für jedes i = 1, . . . , |E| tue:
Für jeden Knoten n ∈ Ni tue:
Wenn (mate_n, i, 0) mit h inkompatibel ist, setze den 0-Kind von n auf 0;
Andernfalls setze den 0-Kind von n auf GN(i + 1, mate_n|V ≥ ei+1);
Wenn (mate_n, i, 1) mit h inkompatibel ist, setze den 1-Kind von n auf 0;
Andernfalls setze den 1-Kind von n auf GN(i + 1, MU(mate_n, ei)|V ≥ ei+1);
Ende
Gebe das erstellte Diagramm zurück;
Ende
¶ Erklärung der neuen Zeilen:
Die neue Addition im Algorithmus besteht darin, dass Kompatibilitätsprüfungen für die Pfade mit den vorgegebenen Einschränkungen (h) durchgeführt werden. Diese Prüfungen verhindern, dass ungültige Pfade weiter verfolgt werden, indem sie sicherstellen, dass der aktuelle Pfad die festgelegten Regeln erfüllt.
Erklärung der neuen Zeilen im Pseudocode:
-
Zeile 6: Wenn der Pfad im Zustand 0 mit den Einschränkungen (h) inkompatibel ist, wird der 0-Kind von n auf 0 gesetzt. Das bedeutet, dieser Pfad wird verworfen und nicht weiterverfolgt.
-
Zeile 8: Wenn der Pfad im Zustand 1 mit den Einschränkungen (h) inkompatibel ist, wird der 1-Kind von n auf 0 gesetzt. Auch dieser Pfad wird verworfen.
¶ Zusammenfassung
Der Algorithmus erweitert Knuths SIMPATH-Algorithmus durch die Prüfung von kompatiblen und inkompatiblen Zuständen vor jeder Entscheidung. Dies gewährleistet:
- Nur kompatible Pfade werden weiter verfolgt.
- Inkompatible Zustände werden frühzeitig ausgeschlossen.
¶ Leistung und Laufzeit für Numberlink[2:6]
In diesem Abschnitt vergleichen wir die Laufzeiten unseres Numberlink-Algorithmus mit den bestehenden Methoden, die CPLEX und Sugar verwenden. Wir haben das Algorithmus für Numberlink in C++ implementiert und mit der -O3-Optimierung kompiliert.
| Instanz | Graph Größe | CPLEX Zeit (s) | Sugar Zeit (s) | Numberlink (SIMPATH) Zeit (s) | Speicher (MB) |
|---|---|---|---|---|---|
| BN52 | G10,10 | 0.45 | 1.520 | 0.012 | 3 |
| BN64 | G10,10 | 108.07 | 1.704 | 0.136 | 11 |
| BN72 | G10,10 | 276.07 | 1.388 | 0.012 | 4 |
| BN79 | G10,10 | 15,117.47 | 1.496 | 0.220 | 37 |
| BN85 | G20,15 | >100,000 | 7,213.079 | 862.518 | 43,846 |
| BN99 | G20,15 | >100,000 | 14.097 | 1,658.772 | 67,094 |
| C88 | G20,36 | >100,000 | >100,000 | – | – |
¶ Beobachtungen:
- Numberlink (SIMPATH) ist extrem schnell bei kleinen Instanzen, wie in BN52 (0.012 Sekunden) zu sehen, wo es die anderen Ansätze (CPLEX und Sugar) deutlich übertrifft.
- Bei größeren Instanzen wie BN85 und BN99 wird Numberlink (SIMPATH) langsamer, insbesondere bei BN85 (862.518 Sekunden), aber es ist immer noch schneller als CPLEX und Sugar, die mit viel längeren Zeiten (>100.000 Sekunden) zu kämpfen haben.
- In BN85 zeigt Numberlink (SIMPATH) eine bessere Performance im Vergleich zu CPLEX und Sugar, die bei dieser großen Instanz extrem hohe Laufzeiten haben. Dies ist eine Ausnahme bei größeren Instanzen.
- Bei anderen großen Instanzen wie BN99 und C88 zeigt Numberlink (SIMPATH) jedoch keine besseren Ergebnisse als CPLEX oder Sugar in Bezug auf die Zeit.
¶ Referenzen
¶ Abbildungsverzeichnis
Abb. 1: anypuzzle, Beispiel für ein Numberlink-Rätsel.URL
Abb. 2: Doug Osborne, Beispiel für ein Numberlink-Rätsel . URL
Abb.3: Yoshinaka, Ryo, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. “Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs.” Algorithms 5, no. 2 (April 5, 2012): 176–213. https://doi.org/10.3390/a5020176.URL