Ein Computer-Nonogramm-Solver wechselt typischerweise zwischen zwei Aufgaben: einzelne Linien unter den aktuellen Constraints lösen und jede neu erzwungene Zelle in die kreuzenden Linien propagieren. Erreicht dieser Prozess einen festen Punkt, bevor das Raster vollständig ist, können stärkere Solver Annahmen testen oder durch die verbleibenden Möglichkeiten verzweigen.
Programme setzen diese Idee unterschiedlich um, doch das Muster Linienanalyse → Propagation → Suche ist ein nützliches Grundmodell.
1. Das Puzzle als Constraints darstellen
Der Solver speichert:
- die Hinweisfolgen aller Zeilen;
- die Hinweisfolgen aller Spalten;
- den aktuellen Zustand jeder Zelle: gefüllt, leer oder unbekannt.
Jede Zeile und Spalte ist zunächst ein eindimensionales Teilproblem: Finde Blockanordnungen, die ihre Hinweise und alle bereits bekannten Zellzustände erfüllen.
Ein vollständiges Raster ist nur gültig, wenn jede Linie mindestens eine kompatible Anordnung besitzt und alle Zellzustände an den Zeilen-/Spaltenschnittpunkten übereinstimmen.
2. Eine Linie lösen
Ein Liniensolver versucht zu bestimmen, welche Zellen durch Hinweise und aktuelle Zustände dieser Linie erzwungen sind.
Dafür gibt es verschiedene Implementierungsstrategien.
Eine praktische Methode, wie sie auch in WebPBNs pbnsolve dokumentiert ist, bestimmt eine legale Platzierung mit möglichst weit zu einem Ende geschobenen Blöcken und eine zweite in Gegenrichtung. Zellen, die vom gleichen Block in beiden Extremplatzierungen belegt werden, sind gefüllt; Zellen, die nachweislich zwischen denselben Blöcken liegen, können leer werden.
Vollständigere Liniensolver können dagegen alle gültigen Linienmuster unter den aktuellen Constraints enumerieren oder per dynamischer Programmierung berechnen und anschließend ihre gemeinsamen Zustände schneiden.
3. Betroffene kreuzende Linien wieder einplanen
Angenommen, ein Zeilensolver beweist, dass R4C7 gefüllt ist.
Spalte 7 besitzt nun neue Information. Eine gute Implementierung muss deshalb nicht blind das gesamte Puzzle von vorne durchsuchen, sondern kann genau diese Spalte zur erneuten Verarbeitung einplanen.
Erzwingt die Spalte anschließend Zellen in Zeile 2 und 8, kommen diese beiden Zeilen auf die Arbeitsliste.
Das ist die programmatische Form desselben Zeile-Spalte-Rhythmus, den Menschen beim Lösen verwenden.
4. Propagieren, bis ein fester Punkt erreicht ist
Der Solver verarbeitet nützliche Linien weiter, bis entweder:
- jede Zelle bestimmt ist;
- ein Widerspruch entsteht;
- keine Linie einen weiteren erzwungenen Zustand liefert.
Der dritte Zustand ist ein fester Punkt unter dem aktuellen Lösungsverfahren. Er bedeutet nicht automatisch, dass das Puzzle mehrere Lösungen hat oder logisch unlösbar ist. Er bedeutet nur, dass dieses Inferenzsystem direkt nicht weiterkommt.
Ein stärkerer Liniensolver kann noch Zellen erzwingen, die ein billigeres Verfahren übersieht.
5. Widersprüche erkennen
Ein Widerspruch liegt vor, wenn aktuelle Annahmen irgendeinen Constraint unmöglich machen.
Beispiele:
- eine Linie besitzt kein gültiges Muster mehr;
- ein bestätigter Block ist länger als sein Hinweis;
- ein notwendiger Block passt nirgendwo mehr hin;
- eine Zelle wird durch inkompatible Zweige gleichzeitig als gefüllt und leer erzwungen.
In pattern-basierter Darstellung ist eine Linie mit null gültigen Mustern unmöglich.
Widerspruchserkennung ist deshalb sowohl für die Validierung von Spielerzuständen als auch für Suchalgorithmen wichtig.
6. Probing oder Suche verwenden, wenn direkte Logik feststeckt
Ein vollständiger allgemeiner Solver muss gegebenenfalls Alternativen untersuchen.
Ein einfaches Tiefensuchverfahren kann:
- eine unbekannte Zelle oder Blockentscheidung auswählen;
- einen legalen Zustand annehmen;
- die Propagation erneut ausführen;
- im Zweig fortfahren, solange er möglich bleibt;
- bei einem Widerspruch zurückspringen.
Bei Probing werden Kandidatenannahmen zunächst nur vorübergehend getestet und ihre Folgen ausgewertet, bevor ein Zweig endgültig übernommen wird. WebPBNs pbnsolve dokumentiert diesen Ansatz ausführlich.
Der entscheidende Unterschied zur menschenorientierten Logik ist, dass ein Computer Suche einsetzen kann, um Vollständigkeit zu garantieren, selbst wenn direkte Deduktionen ausgeschöpft sind.
7. Eindeutigkeit prüfen
Für die Validierung eines Puzzles reicht es nicht, eine Lösung zu finden.
Ein Solver kann nach der ersten Lösung weiter suchen und prüfen, ob eine zweite unterschiedliche vollständige Belegung existiert.
Die Ergebnisse sind:
- null Lösungen → widersprüchliche Hinweismenge;
- eine Lösung → eindeutig;
- zwei oder mehr → mehrdeutig.
Damit sind automatische Solver nicht nur zum Spielen, sondern auch für Konstruktions- und Veröffentlichungsprozesse wertvoll.
Nicht jeder Solver verwendet denselben Algorithmus
Nonogramme lassen sich in mehreren rechnerischen Frameworks modellieren.
Implementierungen können kombinieren:
- spezialisierte Liniensolver;
- dynamische Programmierung;
- Constraint Programming;
- SAT-artige Boolesche Constraints;
- ganzzahlige Programmierung;
- Tiefensuche;
- heuristische Suche;
- Probing und Caching.
Forschung vergleicht spezialisierte Solver und alternative mathematische Formulierungen. Es gibt keine vorgeschriebene einzige Architektur.
Korrekt ist ein Algorithmus dann, wenn er Hinweise und Zellconstraints respektiert und – wenn er Vollständigkeit oder Eindeutigkeit behauptet – genug vom Lösungsraum untersucht, um diese Aussage zu rechtfertigen.
Schnelle Linienlogik vs. vollständige Linienlogik
Eine subtile Implementierungsentscheidung besteht darin, dass ein sehr schneller Liniensolver möglicherweise nicht jede aus einer Linie ableitbare erzwungene Zelle findet.
WebPBN weist ausdrücklich darauf hin, dass seine Links-/Rechts-Overlap-Routine schnell, aber nicht vollständig ist. pbnsolve kann deshalb nach dem Stillstand der gewöhnlichen Linienlogik eine umfassendere Prüfung durchführen.
Das entspricht einer menschlichen Unterscheidung:
- eine billige visuelle Technik findet viele Zellen schnell;
- vollständige Linienmusteranalyse kann zusätzliche Zellen erzwingen, kostet aber mehr Aufwand.
Wie ein Solver Schwierigkeit bewerten kann
Wenn ein Solver seine eigene Arbeit protokolliert, entstehen Merkmale wie:
- Anzahl gelöster Linien;
- Anzahl Propagationsrunden;
- stärkste benötigte Inferenz;
- Anzahl betrachteter Muster;
- Anzahl Probes oder Suchzweige;
- maximale Suchtiefe.
Diese Merkmale können in ein Schwierigkeitsmodell einfließen. Sie beschreiben die Schwierigkeit aber weiterhin relativ zu genau dieser Solver-Architektur.
Warum allgemeines Lösen trotzdem schwierig sein kann
Ein spezialisierter Solver kann gewöhnliche Buch-Nonogramme trivial wirken lassen. Trotzdem ist kein Polynomialzeitverfahren bekannt, das alle möglichen Nonogramm-Instanzen löst, sofern zentrale Annahmen der Komplexitätstheorie nicht zusammenbrechen.
Das ist eine Worst-Case-Aussage und keine Behauptung, dass dein tägliches 15×15-Puzzle einen Supercomputer benötigt.
Was du als Nächstes lernen kannst
Für die Theorie hinter der Worst-Case-Schwierigkeit lies Warum Nonogramme rechnerisch schwierig sind. Für das menschenorientierte Gegenstück zu temporären Annahmen lies noch einmal Widerspruchsdenken.
FAQ
Probieren Nonogramm-Solver einfach jedes Raster aus?
Gute Solver müssen das nicht. Linienconstraints und Propagation eliminieren enorme Mengen von Möglichkeiten, bevor überhaupt Suche nötig wird. Viele veröffentlichte Puzzles lösen sich ohne tiefe Verzweigung.
Kann ein Solver beweisen, dass ein Puzzle eindeutig ist?
Ja, wenn er vollständig genug sucht, um jede alternative Lösung auszuschließen.
Sind Computer- und Menschenmethoden identisch?
Sie überschneiden sich konzeptionell stark, besonders bei Linienlogik und Propagation. Computer können aber wesentlich mehr Kandidatenzustände verwalten und systematische Suche verwenden, die für Menschen sehr mühsam wäre.