Ein Nonogramm hat eine eindeutige Lösung, wenn genau ein vollständig als gefüllt/leer markiertes Raster alle Zeilen- und Spaltenhinweise erfüllt.
Erfüllen zwei oder mehr verschiedene Raster dieselben Hinweise, ist das Puzzle mehrdeutig. Erfüllt gar kein Raster alle Hinweise, ist die Hinweismenge widersprüchlich.
Für ein klassisches veröffentlichtes Logikpuzzle ist Eindeutigkeit normalerweise eine grundlegende Qualitätsanforderung.
Ein minimales mehrdeutiges Nonogramm
Betrachte ein 2×2-Raster mit diesen Hinweisen:
Zeilen: 1, 1
Spalten: 1, 1Es gibt zwei Lösungen:
■ × × ■
× ■ ■ ×Jede Zeile enthält genau eine gefüllte Zelle. Jede Spalte ebenfalls. Nichts in den Hinweisen unterscheidet die beiden Diagonalen.
Das Puzzle ist nicht „schwierig, weil man den Trick nicht sieht“. Es ist unterbestimmt. Beide Antworten sind logisch gültig.
Was bedeutet „eindeutig“ genau?
Eindeutigkeit ist eine Eigenschaft des gesamten Constraint-Systems.
Eine Lösung muss alle Zeilen- und Spaltenbedingungen gleichzeitig erfüllen. Ein Puzzle ist nur dann eindeutig, wenn jedes alternative vollständige Raster mindestens eine dieser Bedingungen verletzt.
Das ist stärker als die Aussage:
- das beabsichtigte Bild passt zu den Hinweisen;
- du persönlich hast eine Lösung gefunden;
- das Endbild ist erkennbar;
- ein bestimmtes Lösungsverfahren hat eine Antwort erreicht.
Eine gültige Lösung zu finden beweist, dass mindestens eine Lösung existiert. Es beweist nicht, dass keine zweite existiert.
Eindeutig bedeutet nicht leicht
Diese Trennung ist entscheidend.
Ein Puzzle kann genau eine Lösung besitzen und sich trotzdem gegen gewöhnliche Zeilen-für-Zeilen- und Spalten-für-Spalten-Deduktionen wehren. Die Lösung kann global vollständig festgelegt sein, obwohl lokal zunächst kein direkter Zug sichtbar ist.
Darum sind diese Aussagen verschieden:
- Das Puzzle besitzt genau eine Lösung.
- Das Puzzle ist mit den Techniken lösbar, die ein bestimmter Mensch oder Solver verwendet.
- Das Puzzle ist für seine Zielgruppe leicht.
Ein Eindeutigkeitschecker beantwortet die erste Frage. Ein Schwierigkeitsmodell und eine Analyse des Lösungswegs beantworten die anderen.
Warum Mehrdeutigkeit entsteht
Mehrdeutigkeit entsteht, wenn die Hinweise einen Teil der Struktur austauschbar lassen.
Typische Ursachen sind:
Symmetrische Alternativen
Zwei Zellgruppen können ihre Positionen tauschen, ohne die Run-Längen in Zeilen und Spalten zu verändern.
Dünne Hinweisstruktur
Viele kurze Hinweise in viel freiem Raum können mehrere Platzierungen erlauben, die durch die kreuzenden Linien nie vollständig unterschieden werden.
Unabhängige Regionen
Ein Puzzle kann zwei ungelöste Teilbereiche enthalten, die jeweils zwischen mehreren Varianten wechseln können, ohne den Rest des Rasters zu beeinflussen.
Bildänderungen, die das Hinweisverhalten erhalten
Nicht jede Änderung am Motiv verstärkt das Constraint-System. Manche verschieben die Unsicherheit nur an eine andere Stelle.
Wie Konstrukteure Eindeutigkeit testen
Bei winzigen Puzzles könnte man theoretisch jedes mögliche Raster prüfen.
Für realistische Größen verwendet Software effizientere Constraint- und Suchverfahren. Ein Solver kann:
- eine vollständige Lösung finden;
- danach gezielt nach einer anderen vollständigen Lösung suchen;
- stoppen, sobald eine zweite gefunden wurde, oder beweisen, dass keine Alternative mehr übrig ist.
Werkzeuge wie WebPBNs pbnsolve nutzen genau diese Art der Validierung für benutzererstellte Puzzles.
Kann Logik beim Lösen Eindeutigkeit beweisen?
Wenn eine Folge korrekter Deduktionen ausschließlich aus den Hinweisen startet und ohne Verzweigung jede Zelle bestimmt, dann ist das erreichte Raster zwangsläufig die einzige Lösung, die mit diesen Constraints vereinbar ist.
Wenn normale Linienlogik jedoch feststeckt, darfst du daraus nicht schließen, dass das Puzzle mehrdeutig ist. Die fehlende Deduktion kann stärkere Linienanalyse, Mehrlinienlogik, Widerspruchsdenken oder Suche benötigen.
Ebenso beweist eine durch Branching gefundene Lösung nicht automatisch Eindeutigkeit. Die nicht untersuchten Zweige sind dafür entscheidend.
Warum ein erkennbares Bild keine Mehrdeutigkeit auflöst
Angenommen, eine gültige Lösung sieht wie eine Katze aus und eine andere wie eine leicht verzerrte Katze.
Die „schönere“ Katze auszuwählen ist keine Nonogramm-Deduktion. Die Hinweise haben diese Entscheidung nicht bewiesen.
Ein korrekt validiertes Puzzle sollte keine ästhetische Vorliebe brauchen, um zwischen mathematisch gültigen Rastern zu wählen.
Das entstehende Bild kann dir Orientierung geben, ist aber niemals ein Beweis für einen Zellzustand.
Eindeutige Lösung vs. eindeutiger Lösungsweg
Eine eindeutige Lösung bedeutet nicht, dass nur eine Reihenfolge von Deduktionen möglich ist.
Zwei Spieler können dasselbe gültige Puzzle unterschiedlich angehen:
- einer beginnt mit einer langen Zeile;
- der andere mit einer stark eingeschränkten Spalte;
- beide erzwingen am Ende dasselbe Raster.
Das Ziel ist eindeutig, obwohl der Weg es nicht ist.
Für Puzzle-Design ist das sogar wertvoll: Ein Nonogramm kann mehrere produktive Einstiege bieten, ohne mehrdeutig zu werden.
Was tun, wenn ein veröffentlichtes Nonogramm mehrere Lösungen hat?
Wenn die Regeln standardmäßig monochrom sind und zwei vollständige Raster wirklich jeden Hinweis erfüllen, ist das Puzzle mehrdeutig – unabhängig davon, welches Bild der Herausgeber beabsichtigt hat.
Bevor du ein Puzzle als fehlerhaft einstufst, prüfe:
- ob die Hinweisreihenfolge eingehalten wird;
- ob aufeinanderfolgende Blöcke korrekt getrennt sind;
- ob jedes X als leer und nicht als unbekannt behandelt wird;
- ob kein gefüllter Block versehentlich länger als sein Hinweis ist;
- ob der Herausgeber nicht doch eine Variantenregel verwendet.
Erfüllen danach weiterhin zwei Raster dieselben Standardhinweise, bestimmen die Hinweise keine eindeutige Antwort.
Was du als Nächstes lernen kannst
Wie solche Fälle algorithmisch erkannt werden, erklärt Wie Computer-Nonogramm-Solver funktionieren. Warum Eindeutigkeit und menschliche Schwierigkeit auseinandergehen können, zeigt Wie Nonogramm-Schwierigkeit bewertet wird.
FAQ
Haben alle Nonogramme genau eine Lösung?
Nein. Eine beliebige Hinweismenge kann null, eine oder mehrere Lösungen besitzen. Gut konstruierte veröffentlichte Puzzles zielen normalerweise auf genau eine.
Bedeutet Feststecken, dass das Puzzle mehrere Lösungen hat?
Nein. Es kann einfach eine Deduktion fehlen, die du noch nicht gefunden hast, oder ein stärkeres Verfahren nötig sein.
Kann ein Nonogramm eindeutig sein und trotzdem Raten erfordern?
Es kann eindeutig sein und zugleich ein bestimmtes lokales Lösungsmodell überfordern. Ob stärkere Fallanalyse als „Raten“ bezeichnet wird, hängt davon ab, wie sauber sie begründet wird; G-011 trennt unbegründetes Raten von Widerspruchsbeweisen.