Templates
Verwandte der Pattern Overlay Method. Zählt gültige Platzierungs-Templates auf und nutzt paarweise Inkompatibilität für Eliminierungen, die ein einzelnes Template verfehlt.
Templates ist eine enge Verwandte der Pattern Overlay Method, die dieselben aufgezählten Platzierungsmuster nutzt, aber mit einem zusätzlichen Schritt. Wo POM alle Muster vereinigt und Zellen eliminiert, die in der Vereinigung fehlen, untersucht Templates Paare von Templates — eines für jede von zwei verschiedenen Ziffern — und sucht nach Inkompatibilitäten. Wenn die Ziffer a, platziert über das Template T1, mit jeder möglichen Platzierung der Ziffer b unter jedem ihrer überlebenden Templates kollidiert, ist T1 selbst unmöglich und kann aus dem Suchraum eliminiert werden, was wiederum die Vereinigung für Ziffer a verkleinert.
Wie sie sich von Pattern Overlay unterscheidet
POM arbeitet eine Ziffer nach der anderen. Die Eliminierungsmenge jeder Ziffer wird allein aus ihrer eigenen Template-Aufzählung berechnet. Templates führt ziffernübergreifende Argumentation ein: Ein Template für Ziffer a ist ungültig, wenn es a in Zellen platziert, in denen jedes Template für Ziffer b b kollidierend platzieren müsste. Viele Template-Paare, die einzeln für ihre eigene Ziffer konsistent sind, scheitern in der Kombination.
Das Verfahren: Prüf für jedes Paar (a, b) von Ziffern, für jedes Template T_a der Ziffer a, ob mindestens ein Template T_b der Ziffer b verträglich ist (keine zwei Zellen in derselben Zeile, Spalte oder demselben Block halten a und b in kollidierenden Positionen). Existiert kein verträgliches T_b, wird T_a aus der Suche eliminiert. Wiederhol über alle Ziffernpaare und iterier bis zur Konvergenz.
Warum sie schwerer ist als POM
Die Kombinatorik wird schnell teuer. POM macht höchstens 9 Aufzählungen; Templates macht bis zu 36 paarweise Prüfungen (die Anzahl der Ziffernpaare), von denen jede jedes Template einer Ziffer mit jedem Template einer anderen vergleicht. Auf einem schweren Rätsel mit mehreren hundert Templates pro Ziffer kann Templates feuern, wo POM es nicht tut — aber die Laufzeitkosten sind mehrere Größenordnungen höher.
Die meisten Software-Löser laufen Templates nicht standardmäßig. Sie reservieren sie für die kleine Menge von Rätseln, in denen POM sich erschöpft und ein Brute-Force-Löser sonst der nächste Schritt wäre. Manuelle Löser laufen Templates überhaupt nicht — die paarweise Aufzählung ist sogar für Software unpraktikabel, geschweige denn von Hand.
Die Beziehung zur fortgeschrittenen Kettenargumentation
Die ziffernübergreifende Inkompatibilitätsprüfung von Templates ist konzeptionell ähnlich zu bestimmten AIC-Mustern, die mehrere Ziffern überspannen, und zur ziffernübergreifenden Farb-Propagation in 3D Medusa. Der Unterschied liegt in der Abstraktionsebene: AIC und Medusa arbeiten auf der Ebene benannter Muster und Kettenlinks, während Templates auf der Ebene vollständiger Gitter-Platzierungen arbeitet. Theoretisch sind dieselben Eliminierungen über sauberere Kettenlogik erreichbar; in der Praxis sind manche leichter über Aufzählung zu finden als über Mustererkennung.
Für die meisten Löser steht der Templates-Eintrag hier eher der Vollständigkeit halber als als tägliches Werkzeug. Die Verwandte POM ist die häufiger zitierte der beiden Techniken.
Siehe auch
- Pattern Overlay Method (POM)— Eine erschöpfende Technik, die jedes legale Platzierungsmuster einer einzelnen Ziffer aufzählt und dann Kandidaten eliminiert, die in keinem Muster auftauchen.
- Nishio— Eine Probier-und-Widerspruchs-Technik. Wähl einen Kandidaten, nimm an, er sei die Antwort, propagier die Folgen für diese Ziffer allein — landet ein Widerspruch, eliminier.
- Kandidat— Eine Ziffer (1–9), die eine Zelle legal aufnehmen könnte — noch nicht ausgeschlossen durch Zeile, Spalte oder Block. Jede leere Zelle hat zwischen einem und neun.