Beim eigentlichen Spielen brauchen Nonogramme nur wenig Arithmetik. Unter der Oberfläche steckt jedoch ein kompaktes kombinatorisches Constraint-Problem.
Jeder Hinweis beschreibt geordnete Blöcke gefüllter Zellen in einer Linie. Zeilen- und Spaltenbedingungen überlagern sich auf denselben Zellen, und die Lösung ist genau das binäre Raster, das alle diese Bedingungen gleichzeitig erfüllt.
Hinweise sind Run-Length-Beschreibungen
Eine Hinweisfolge speichert die Längen aufeinanderfolgender gefüllter Blöcke.
Zum Beispiel:
■■■ ×× ■■ × ■
3 2 1Die Zahlen verraten nicht, wo die Blöcke beginnen. Sie legen fest:
- die Blocklängen;
- die Blockreihenfolge;
- dass benachbarte monochrome Blöcke mindestens durch eine leere Zelle getrennt sein müssen.
Darum ist eine Hinweisfolge mehr als nur ihre Summe.
Mindestplatz
Angenommen, eine Linie besitzt m Hinweisblöcke mit den Längen:
c1, c2, ..., cmDie gefüllten Zellen benötigen:
c1 + c2 + ... + cmZellen. Zwischen den m aufeinanderfolgenden Blöcken gibt es m - 1 Grenzen, die jeweils mindestens eine leere Zelle benötigen.
Daher ist der kürzeste Bereich, in den alle Hinweise passen:
Mindestplatz = sum(clues) + (Anzahl der Hinweise - 1)Für eine 10-Zellen-Linie mit 3 2 gilt:
Mindestplatz = 3 + 2 + 1 = 6Die Linie besitzt also vier Zellen zusätzliche Platzierungsfreiheit.
Dieser zusätzliche Raum ist der Spielraum.
Wie viele Platzierungen kann eine Hinweisfolge auf einer leeren Linie haben?
Auf einer ansonsten vollständig unbekannten monochromen Linie kann der Spielraum verteilt werden:
- vor dem ersten Block;
- nach dem letzten Block;
- als zusätzliche leere Zellen in jedem verpflichtenden Zwischenraum zwischen Blöcken.
Bei m Blöcken und Spielraum s beträgt die Anzahl vollständiger Platzierungen:
C(s + m, m)wobei C der Binomialkoeffizient ist.
Beispiel: Länge 10 mit Hinweisen 3 2
Wir haben bereits:
Mindestplatz = 6
Spielraum = 10 - 6 = 4
m = 2Damit besitzt die vollständig unbekannte Linie:
C(4 + 2, 2) = C(6, 2) = 15legale vollständige Muster.
Diese Zahl gilt für die noch unbeschränkte Ausgangslinie. Sobald einige Zellen als gefüllt oder leer bekannt sind, können viele der 15 Muster wegfallen.
Warum Überlappung mathematisch funktioniert
Eine Zelle ist erzwungen gefüllt, wenn jedes unter den aktuellen Constraints gültige Muster diese Zelle füllt.
Entsprechend ist eine Zelle erzwungen leer, wenn jedes gültige Muster sie leer lässt.
Überlappung ist eine schnelle menschliche Methode, einige dieser gemeinsamen Zellen zu finden, ohne alle Muster explizit aufzulisten.
Die fortgeschrittenere Technik der gültigen Linienmuster macht denselben Gedanken vollständig sichtbar: Bestimme die Menge legaler Muster und übernimm alle Zustände, in denen sie übereinstimmen.
Zeilen und Spalten bilden kreuzende Constraints
Eine einzelne Linie ist nur ein Teilproblem.
Jede Zelle gehört gleichzeitig zu:
- genau einer Zeile;
- genau einer Spalte.
Wenn eine Zeile eine Zelle als gefüllt erzwingt, wird dieser Zustand sofort zu einer zusätzlichen Bedingung für die kreuzende Spalte. Dort fallen dadurch Muster weg. Das kann neue gemeinsame Zustände erzeugen, die wiederum andere Zeilen einschränken.
Diese wiederholte Wechselwirkung ist die mathematische Grundlage von Kreuzreferenzierung und Constraint-Propagation.
Ein Nonogramm wird nicht durch Addieren der Hinweise gelöst
Die Summe der Hinweise verrät, wie viele gefüllte Zellen eine Linie enthält. Sie verrät aber nicht ihre Positionen.
Bei 3 2 auf einer Zehnerlinie wissen wir, dass fünf Zellen gefüllt sind. Ohne weitere Information gibt es trotzdem 15 verschiedene vollständige Muster.
Erst Reihenfolge, verpflichtende Trennung, Randgrenzen und kreuzende Zellzustände reduzieren diese Menge.
Das ist auch der Grund, warum eine große Hinweissumme eine Linie zwar oft stark einschränkt, aber nicht automatisch vollständig bestimmt.
Kombinatorik wächst schnell
Schon einzelne Linien können viele Muster besitzen. Im ganzen Raster müssen Kombinationen von Zeilenmustern gleichzeitig zu Kombinationen von Spaltenmustern passen.
Ein naives Verfahren, das einfach jedes vollständige Raster ausprobiert, würde bei N Zellen grundsätzlich bis zu 2^N binäre Zustände berücksichtigen müssen.
Praktische Solver tun das nicht. Sie nutzen die Struktur der Hinweise, dynamische Programmierung, Propagation und Suche mit starker Beschneidung.
Trotzdem erklärt das schnelle Wachstum der Kombinationsräume, warum das allgemeine Nonogramm-Problem schwierige Instanzen enthalten kann.
Warum diese Mathematik Menschen beim Lösen hilft
Du musst beim Spielen keine Binomialkoeffizienten ausrechnen.
Die mathematische Sicht erklärt aber, warum vertraute Techniken funktionieren:
- wenig Spielraum bedeutet wenige Platzierungen;
- Überlappung findet die Schnittmenge dieser Platzierungen;
- Blockreichweite beschreibt ihre Vereinigungsmenge;
- X-Markierungen entfernen Muster;
- kreuzende Informationen reduzieren die Pattern-Mengen;
- Propagation wiederholt diese Reduktion bis zum festen Punkt.
Die Formeln ersetzen die praktische Logik nicht. Sie machen ihre Struktur sichtbar.
Ist ein Nonogramm ein Mathe-Puzzle?
Es ist sinnvoll, Nonogramme als Logikpuzzles mit mathematischer Struktur zu beschreiben.
Beim normalen Lösen steht Deduktion im Vordergrund, nicht Rechnen. Formal lassen sich die Regeln aber mit Kombinatorik, binären Variablen und Constraints modellieren.
Beide Perspektiven sind richtig und beschreiben unterschiedliche Ebenen desselben Puzzles.
Was du als Nächstes lernen kannst
Für die praktische Bedeutung von Mindestplatz und Spielraum lies Mindestplatz und Spielraum.
Für vollständige Linienmengen lies Gültige Linienmuster.
Für die algorithmische Sicht lies Wie Computer-Nonogramm-Solver funktionieren.
Für die Worst-Case-Perspektive lies Warum Nonogramme rechnerisch schwierig sind.
FAQ
Wie lautet die Mindestplatz-Formel für Nonogramm-Hinweise?
Bei m monochromen Blöcken: Summe aller Blocklängen plus m - 1 verpflichtende Trennzellen.
Gilt die Formel für die Anzahl der Platzierungen immer?
Nein. C(s + m, m) gilt für eine ansonsten vollständig unbekannte Linie ohne zusätzliche Zellconstraints. Bekannte gefüllte oder leere Zellen eliminieren einen Teil dieser Muster.
Muss ich Kombinatorik können, um Nonogramme zu lösen?
Nein. Die üblichen menschlichen Techniken verkörpern diese Ideen bereits in praktischer Form.