Constraint-Propagation und Kaskaden

Constraint-Propagation ist der wiederholte Prozess, neue sichere Zellzustände an ihre kreuzenden Linien weiterzugeben, dort sämtliche erzwungenen Folgen zu bestimmen und so lange fortzufahren, bis keine unmittelbare Schlussfolgerung mehr entsteht.

Eine Kaskade ist die sichtbare Kette dieser Folgeschlüsse.

Ein Fünf-mal-fünf-Beispiel für eine Kaskade

Betrachte ein monochromes 5×5-Nonogramm mit:

Zeilen: 1, 3, 5, 3, 1

Spalten: 1, 3, 5, 3, 1

Zeile 3 ist eine exakte Einpassung: Hinweis 5 füllt die ganze Zeile.

Nun propagierst du:

1. Spalten 1 und 5 haben jeweils Hinweis 1; ihre mittlere Füllung erfüllt den Hinweis bereits, daher werden alle anderen Zellen dort leer;
2. Spalte 3 hat Hinweis 5 und füllt sich vollständig;
3. Zeilen 1 und 5 besitzen nun ihre einzige notwendige Füllung in Spalte 3, alle übrigen Zellen werden leer;
4. Spalten 2 und 4 mit Hinweis 3 müssen jetzt Zeilen 2–4 füllen;
5. Zeilen 2 und 4 werden dadurch vollständige Dreierblöcke.

Eine einzige direkte Anfangsschlussfolgerung löst das gesamte Raster durch Propagation.

Propagation ist keine eigene Wahrheitsquelle

Jeder einzelne Schritt benutzt weiterhin gewöhnliche, gültige Nonogramm-Logik: exakte Einpassung, abgeschlossene Blöcke, Überlappung, Lückenausschluss, Musterfilterung und so weiter.

Propagation beschreibt wie diese Schlüsse organisiert und über das gemeinsame Raster verkettet werden.

Warum Kaskaden schneller sind als permanentes Vollscannen

Wenn sich eine Zelle ändert, erhalten zunächst nur ihre Zeile und Spalte direkt neue Information.

Statt das gesamte Puzzle wieder bei Zeile 1 zu beginnen, folgst du den betroffenen Linien. Erzeugt eine davon eine weitere neue Zelle, prüfst du deren senkrechte Linie als Nächstes.

So konzentrierst du deine Aufmerksamkeit genau dort, wo sich das Constraint-System tatsächlich verändert hat.

Beide Arten von Sicherheit propagieren

Kaskaden werden von Füllungen und X-Markierungen angetrieben.

Zum Beispiel:

• eine Füllung verankert einen Block;
• ein X teilt ein Segment;
• die Segmentteilung ordnet einen Hinweis zu;
• die Zuordnung erzeugt eine exakte Einpassung;
• diese Einpassung schließt einen senkrechten Block ab;
• dessen Trennzelle schließt eine weitere Lücke aus.

Leere Zellen sind kein „sekundärer Fortschritt“. Beide Zustände reduzieren die Menge legaler Muster.

Stoppe erst an einem stabilen Zustand

Ein Propagationsdurchlauf ist abgeschlossen, wenn jede Linie, die durch neue Zellen verändert wurde, erneut ausgewertet ist und keine weitere sichere Änderung mehr folgt.

In Solver-Sprache nennt man einen solchen Zustand häufig festen Punkt (fixed point): Würdest du dieselben lokalen Regeln erneut anwenden, bliebe das Raster unverändert.

Erst dann suchst du eine neue aussichtsreiche ungelöste Linie oder verwendest bei wirklich schwierigen Puzzles stärkere Logik.

Eine Kaskade kann ohne exakte Einpassung beginnen

Das Diamantbeispiel startet mit einer offensichtlichen vollen Linie. Interessanter sind Kaskaden, die nur mit einer schwächeren Konsensschlussfolgerung beginnen.

Betrachte dieses 5×5-Puzzle:

Zeilen: 2 1, 1 1, 2, 2, 1 1

Spalten: 1 2, 1 2, 2, 1, 2

Zu Beginn ist keine Zeile und keine Spalte eine exakte Einpassung. Trotzdem besitzt Zeile 1 mit Hinweis 2 1 eine Zelle, die in jedem gültigen Anfangsmuster gefüllt ist: Zelle 2.

Markiere R1C2 gefüllt und propagiere nur Zustände, auf die sich jeweils alle gültigen Linienmuster einigen. Die neue Information reduziert Spalte 2; diese erzeugt neue Zustände in Zeilen 2 und 4; diese wiederum schränken weitere Spalten ein. Die Kaskade läuft weiter, bis das gesamte Raster feststeht.

Die eindeutige Lösung ist:

■■××■

××■×■

×■■××

■■×××

■××■×

Das zeigt: Propagation bedeutet nicht „erst alle einfachen Zeilen lösen“. Eine kleine lokale Konsensinformation kann durch das gemeinsame Raster immer wieder verstärkt werden.

Nutze eine Warteschlange geänderter Linien

Ein präzises Modell für manuelle Propagation ist eine Queue:

1. Ändert sich eine Zelle, setze Zeile und Spalte auf die Warteschlange.
2. Werte eine geänderte Linie gegen den aktuellen Zustand aus.
3. Erzwingt sie neue Zellen, setze deren senkrechte Linien ebenfalls auf die Queue.
4. Entferne die verarbeitete Linie.
5. Wiederhole, bis die Warteschlange leer ist.

Eine Linie darf mehrfach zurückkehren, wenn spätere Kreuzinformationen sie erneut verändern. Genau so vermeiden auch viele Solver unnötige Neuberechnungen.

Wichtig: Ein fester Punkt ist immer relativ zur Stärke der verwendeten Linienlogik. Wenn du nur einfache Überlappung propagierst, kannst du früher stehen bleiben als mit vollständiger Musteranalyse. Ein stärkerer Liniensolver, der alle gültigen Muster berücksichtigt, kann noch neue Zellen finden und die Kaskade erneut starten.

Deshalb kann ein Puzzle scheinbar feststecken, obwohl kein Raten nötig ist.

Propagation und gültige Linienmuster

Musterlogik liefert eine saubere formale Sicht.

Jede Zeile und Spalte besitzt eine Menge gültiger Muster. Wird eine Zelle sicher gefüllt oder leer:

1. verschwinden inkompatible Muster aus der senkrechten Linie;
2. die Restmuster stimmen möglicherweise an einer weiteren Zelle überein;
3. diese neue sichere Zelle filtert die nächste senkrechte Linie;
4. der Prozess wiederholt sich.

Genau das ist eine logische Kaskade.

Praktischer Propagationsablauf

1. Halte eine kleine mentale Liste der Linien, die durch deinen letzten Zug verändert wurden.
2. Verarbeite eine geänderte Linie mit der stärksten passenden Linienlogik.
3. Markierst du eine neue Zelle, setze ihre senkrechte Linie auf deine Liste.
4. Prüfe unveränderte Linien nicht unnötig immer wieder.
5. Arbeite weiter, bis die Liste keine neuen Zustände erzeugt.
6. Kehre danach zum breiteren Scannen zurück und suche den nächsten Einstiegspunkt.

Auf großen Puzzles ist dieser Ablauf deutlich effizienter, als nach jedem Zug wieder von oben zu beginnen.

Häufige Fehler

Nach der ersten Folge stoppen

Eine neue Zelle kann mehrere weitere Schritte auslösen. Folge der Kette bis zum stabilen Zustand.

Eine unsichere Annahme wie eine Tatsache propagieren

Normale Propagation benutzt bestätigte Zustände. Testest du bewusst eine Annahme, muss dieser Zweig klar getrennt bleiben; das gehört zum Widerspruchsdenken.

Kaskaden durch Leerzellen ignorieren

Ein X kann genau der Schritt sein, der eine Linie segmentiert oder einen Block abschließt.

Jede Linie wahllos neu prüfen

Priorisiere Linien, die durch neue Zellen wirklich Information erhalten haben.

Was du als Nächstes lernen solltest

Erreicht selbst starke Propagation einen stabilen Zustand und bleiben Zellen ungelöst, können Expertenpuzzles kontrollierte Annahmen erfordern: einen Kandidatenzustand testweise setzen, nur sichere Folgen propagieren und ihn verwerfen, wenn eine harte Unmöglichkeit entsteht. Das ist Widerspruchsdenken.

FAQ

Ist Constraint-Propagation dasselbe wie Kreuzreferenzierung?

Kreuzreferenzierung ist eine einzelne Informationsübertragung zwischen senkrechten Linien. Propagation ist die systematische Wiederholung solcher Übertragungen bis zum festen Punkt.

Gehört Raten zur Propagation?

Nein. Standard-Propagation arbeitet nur mit bereits bewiesenen Zellzuständen.

Kann eine einfache Schlussfolgerung ein ganzes Puzzle lösen?

Ja. Manche Nonogramme enthalten lange Kaskaden, bei denen eine frühe sichere Linie genug Folgen auslöst, um das gesamte Raster fertigzustellen.