Pattern Overlay Method (POM)

Die Pattern Overlay Method, meist POM abgekürzt, ist eine an Brute-Force grenzende Technik, die jedes mögliche Platzierungsmuster einer einzelnen Ziffer übers Gitter aufzählt. Ein „Muster" ist eine Menge von neun Zellen — eine in jeder Zeile, eine in jeder Spalte, drei pro Block — in denen die Ziffer legal platziert werden könnte, ohne mit den vorhandenen Vorgaben oder Kandidatenbeschränkungen des Rätsels zu kollidieren. POM listet jedes gültige Muster für die Ziffer auf und nimmt dann die Vereinigung der Zellen, in denen die Ziffer über alle Muster hinweg auftaucht. Jede Kandidatenzelle der Ziffer, die in keinem Muster auftaucht, kann eliminiert werden.

Wie die Aufzählung läuft

Generier für jede der Ziffern 1–9 alle möglichen „Templates" — Platzierungskonfigurationen, die die Zeilen-/Spalten-/Blockbedingungen von Sudoku erfüllen. Auf einem unbearbeiteten Gitter gibt es 5.472.730.538 solcher Templates pro Ziffer; auf einem teilweise gelösten Gitter sinkt die Zahl deutlich, oft ins Dutzend oder die niedrigen Hunderte. Die Aufzählung schneidet sich mit dem Kandidatenstand: Nur Templates, die mit den aktuellen Notizen verträglich sind, werden behalten.

Sobald die Aufzählung fertig ist, ist die Eliminierung der POM mechanisch. Prüf für jede Zelle jedes überlebende Template — platziert mindestens eines die Ziffer dort? Wenn ja, lass den Kandidaten. Wenn nein, eliminier ihn. Dasselbe Verfahren läuft für jede Ziffer unabhängig.

Warum sie an der Kante einer „Technik" sitzt

POM ist technisch eine Deduktion — jede Eliminierung, die sie feuert, ist eine logische Folge der Rätselregeln —, aber sie ist auch rechnerisch in einer Weise schwer, in der andere Techniken es nicht sind. Die anderen benannten Muster (X-Wing, AIC, ALS-XZ) sind alle spezifische logische Muster, deren Anwesenheit im Gitter direkt Eliminierungen produziert. POM zählt jeden möglichen Zustand auf und schneidet sie.

Manche Löser-Communities lehnen POM mit der Begründung ab, sie sei eigentlich keine Technik — sie sei nur erschöpfende Suche im Anzug. Andere akzeptieren sie, weil die Eliminierungen gültig sind und das Verfahren wohldefiniert ist. Die mittlere Position ist, dass POM ein nützliches Diagnoseinstrument für Software-Löser ist: Wenn auf einem gegebenen Rätselzustand kein menschenerkennbares Muster feuert, sagt POM dir, ob irgendwelche Eliminierungen noch zu finden sind, bevor man auf echte Brute-Force zurückfällt.

Wann du sie siehst

Manuell wirst du sie nicht sehen. POM ist auf jedem Rätsel schwerer als leicht von Hand unpraktikabel. Software-Löser nutzen sie als Rückfall, wenn die menschenerkennbaren Techniken in ihrer Hierarchie ausgehen, und als Maßstab für die Schwierigkeitsmessung (ein Rätsel „braucht POM", wenn seine einzigen verbleibenden Eliminierungen aus Muster-Schnitten kommen statt aus benannten Mustern).

Für eine eng verwandte Technik auf derselben konzeptionellen Stufe, siehe Templates.