3D Medusa
Färbungstechnik, die den Strong-Link-Graphen jeder Ziffer gleichzeitig zweifarbig einfärbt und ziffernübergreifende Eliminierungen findet, die einzelfarbige Ketten verfehlen.
3D Medusa ist die Färbungstechnik, die Simple Coloring und Multi-Coloring zu einem einzigen vereinheitlichten Schema verallgemeinert. Wo Simple Coloring den Strong-Link-Graphen einer Ziffer zweifarbig einfärbt und Multi-Coloring sich auf mehrere disjunkte Ketten derselben Ziffer ausweitet, färbt 3D Medusa den Graphen jeder Ziffer gleichzeitig — und fügt die ziffernübergreifende Bedingung hinzu, dass innerhalb einer Zelle jeder Kandidat eine Farbe erbt und die Farben konsistent sein müssen.
Was „3D" hier bedeutet
Das „3D" im Namen verweist auf die konzeptionelle dritte Achse. Simple Coloring läuft in zwei Dimensionen: über die Zeilen und Spalten des Gitters, zweifarbig für eine Ziffer. Multi-Coloring läuft in zwei Dimensionen, aber auf mehreren Ketten. 3D Medusa fügt eine dritte Achse hinzu — die Ziffer-Dimension — und propagiert Farbinformation über Ziffern hinweg, sobald eine Zelle mehrere Kandidaten hat.
Die Regel ist im Konzept einfach. Wenn eine Zelle zwei Kandidaten a und b hat und a in seinem Strong-Link-Graphen die Farbe A trägt, dann erbt b die gegenüberliegende Farbe B (denn genau einer der Kandidaten der Zelle ist die Antwort, und die Strong-Link-Farbe A heißt „dieser Kandidat ist die Ziffer, wenn jede A-gefärbte Zelle es ist"). Die Farb-Propagation läuft übers Gitter weiter und nimmt Implikationen zwischen Ziffern über geteilte Zellen mit.
Die Eliminierungen
Drei Familien von Eliminierungen feuern aus einem 3D Medusa:
- Gleichfarbige Kollision in einer Einheit. Zwei Zellen derselben Farbe teilen sich eine Einheit — die Farbe ist unmöglich, eliminier sie überall.
- Zwei gegenüberliegende Farben in einer Zelle auf verschiedenen Ziffern. Eine Zelle hält die Kandidaten a (Farbe A1) und b (Farbe B2). A1 und B2 sind eingeschränkt: Wenn A1 die Wahrheit ist, muss die Zelle a sein; wenn B2 die Wahrheit ist, muss die Zelle b sein. Andere Kandidaten der Zelle dürfen eliminiert werden.
- Ein Kandidat sieht beide Farben seiner eigenen Ziffer. Standard-Eliminierung à la Simple Coloring, verallgemeinert über die einheitliche Färbung.
Die ersten zwei erweitern die Reichweite der Einzelziffer-Färbung deutlich. Ein 3D Medusa produziert oft mehrere Eliminierungen aus einem Muster, wo Simple Coloring nur eine oder zwei pro Ziffernkette geliefert hätte.
Wann es den Aufwand wert ist
3D Medusa ist von Hand schwer aufzusetzen. Den Strong-Link-Graphen jeder Ziffer zweifarbig einzufärben und die ziffernübergreifende Farbvererbung zu verfolgen, ist viel Buchführung. Die meisten Löser greifen erst dann dazu, wenn AIC und die benannten Einzelziffer-Muster ausgeschöpft sind. Software-Löser laufen es günstig, weil die Farb-Propagation mechanisch ist; dort verdient sich 3D Medusa seinen Platz in der Technikhierarchie der gründlicheren Open-Source-Löser.
Für die meisten Extrem-Rätsel überschneiden sich die Eliminierungen, die ein 3D Medusa produziert, mit denen, die eine sorgfältige AIC-Suche sowieso gefunden hätte. Der Wert der Technik liegt darin, einen einzigen vereinheitlichten Algorithmus zu haben, der sie findet, ohne Ketten von Hand aufzuzählen.
Siehe auch
- Simple Coloring— Eine Technik, die den Strong-Link-Graphen einer einzelnen Ziffer zweifarbig einfärbt und dann Kandidaten eliminiert, die beide Farben sehen — der Einstieg in die Kettenlogik.
- Multi-Coloring— Eine Erweiterung von Simple Coloring auf zwei oder mehr disjunkte Ketten derselben Ziffer, die Eliminierungen findet, wenn die Ketten aus der Distanz miteinander interagieren.
- Alternating Inference Chain (AIC)— Die universelle Kettentechnik. Wechselt entlang einer Kandidatenfolge zwischen Strong und Weak Links und eliminiert eine Ziffer aus jeder Zelle, die beide Endpunkte sieht.
- Strong Link— Beziehung zwischen zwei Zellen einer Einheit, in der eine Ziffer genau eine von beiden besetzen muss — das Grundelement, auf dem versteckte Einer, X-Wings und Ketten aufbauen.