2.4 Constraint Satisfaction

Worum geht’s#

Die bisherigen Suchverfahren dieses Kapitels behandeln einen Zustand als undurchsichtige Blackbox: A* (2.1) oder die uninformierte Suche (2.2) kennen nur „Nachfolger” und „Zieltest”, nicht aber den inneren Aufbau einer Lösung. Beim Constraint Satisfaction Problem (CSP) dreht man diese Sicht um. Eine Lösung ist kein anonymer Knoten, sondern eine Belegung mehrerer Variablen, und das Problem wird allein dadurch beschrieben, welche Kombinationen von Werten verboten sind — durch die titelgebenden Constraints.

Mich hat an diesem Thema gereizt, dass diese eine Verlagerung der Perspektive — von „wie komme ich zum Ziel” hin zu „welche Bedingungen muss das Ziel erfüllen” — einen praktischen Unterschied macht. Weil die Struktur des Problems jetzt offenliegt, kann der Löser sie ausnutzen: Er sieht, welche Variable am stärksten eingeschränkt ist, und er kann die Folgen einer Festlegung vorausberechnen, bevor er sie blind weiterverfolgt. Genau das ist der Grund, warum ein allgemeiner CSP-Löser ein Kryptorätsel um Größenordnungen schneller knackt als eine naive Tiefensuche — ganz ohne Wissen über Kryptorätsel. Das CSP ist damit das Paradebeispiel dafür, dass strukturiertes Suchen schlägt blindes Suchen.

Kernkonzepte#

Das Modell: Variablen, Domänen, Constraints#

Der klassische Modellfall ist die Kartenfärbung: Färbe die Bundesstaaten Australiens mit drei Farben so, dass benachbarte Staaten verschiedene Farben tragen. Die Variablen sind die Staaten, die Domäne ist $\{\text{rot}, \text{grün}, \text{blau}\}$, und für jedes Paar benachbarter Staaten $u, v$ gilt das Constraint $u \neq v$. Solche binären Constraints (zwei Variablen) lassen sich als Constraint-Graph zeichnen: Knoten sind Variablen, eine Kante steht für ein Constraint zwischen zwei Variablen. Dieser Graph ist nicht bloß Illustration — seine Topologie steuert später die Heuristiken.

CSP als Suchproblem#

Ein CSP ist ein Spezialfall der Zustandsraumsuche: Ein Zustand ist eine partielle Belegung, der Anfangszustand die leere Belegung, ein Nachfolger entsteht durch Zuweisen eines Werts an eine noch freie Variable, und das Ziel ist eine vollständige, konsistente Belegung. Die naive Variante „Generate & Test” erzeugt alle $\prod_i |D_i|$ vollständigen Belegungen und prüft jede — für $n$ Variablen mit je $d$ Werten sind das $d^n$ Kandidaten, hoffnungslos.

Schon eine kleine Beobachtung ändert alles: Sobald eine partielle Belegung ein Constraint verletzt, kann keine ihrer Erweiterungen mehr konsistent werden. Man muss also nicht erst fertig belegen, um zu scheitern. Das führt unmittelbar zur

Backtracking ist damit nichts anderes als die DFS aus 2.2, angereichert um den Konsistenztest — der Berührungspunkt zum vorigen Thema, auf den ich in den Querbezügen zurückkomme.

Heuristiken: dieselbe Struktur, viel weniger Sackgassen#

Der entscheidende Hebel ist, dass die Constraints den Suchraum strukturieren und der Löser diese Struktur lesen kann — und zwar anwendungsunabhängig. Drei Heuristiken aus dem Foliensatz spielen zusammen:

• Minimum Remaining Values (MRV): Belege als Nächstes die Variable mit der kleinsten Restdomäne. Anschaulich: Pack das engste Teilproblem zuerst an, damit ein unvermeidlicher Fehlschlag früh statt tief im Baum auffällt.
• Grad-Heuristik: Bei Gleichstand wähle die Variable, die an den meisten Constraints beteiligt ist (höchster Knotengrad im Constraint-Graphen) — sie schränkt die meisten anderen ein. Im Australien-Beispiel ist das SA mit fünf Nachbarn.
• Least Constraining Value (LCV): Probiere bei der Wertwahl zuerst den Wert, der den Nachbarn die meisten Optionen lässt.

MRV/Grad steuern also welche Variable, LCV welcher Wert. Der Foliensatz beziffert den Effekt drastisch: bei 48 Variablen sinkt die Zahl der Sackgassen von 1371 (Variablen mit wenigen Nachbarn zuerst) auf 3 (Grad-Heuristik).

Constraint-Propagierung und Kantenkonsistenz#

Heuristiken wählen klug, vermeiden aber nicht das eigentliche Übel: Backtracking erkennt einen Konflikt erst, wenn er eintritt. Forward Checking zieht diese Erkennung vor — nach jeder Belegung streicht es die dadurch unmöglich gewordenen Werte aus den Domänen der Nachbarn; wird eine Domäne leer, wird sofort zurückgesetzt. Forward Checking sieht jedoch nur einen Schritt weit: Es bemerkt nicht, wenn zwei noch freie Variablen sich gegenseitig in eine Sackgasse treiben.

Genau das leistet die Kantenkonsistenz (Arc Consistency). Sie betrachtet jedes binäre Constraint als zwei gerichtete Kanten und macht jede einzeln konsistent:

Der AC-3-Algorithmus stellt Kantenkonsistenz für das ganze Netz her: Er verwaltet eine Arbeitsliste aller Kanten, prüft jede mit arc-reduce, und sobald eine Domäne $\mathrm{dom}(A)$ schrumpft, kommen alle eingehenden Kanten $a(B, A)$ erneut in die Liste — denn die Reduktion könnte deren Konsistenz zerstört haben. Bricht eine Domäne auf die leere Menge zusammen, hat das CSP keine Lösung. Bei $n$ Knoten und Domänengröße $d$ ist der Aufwand $\mathcal{O}(n^2 d^3)$ — polynomial, also billig im Vergleich zur exponentiellen Suche, die er einspart.

Praxis#

Um die Theorie nicht nur zu glauben, habe ich in reinem Python (keine CSP-Bibliothek) einen generischen Backtracking-Löser gebaut, der wahlweise mit AC-3-Propagierung läuft, und damit die Aufgaben von Blatt 6 nachgerechnet. Der Kern ist eine knappe rekursive Funktion; Variablenwahl per MRV, Propagierung per AC-3:

def _backtrack(self, assign, domains, solutions, propagate, find_all):
    self.nodes += 1                                  # Suchknoten zählen
    if len(assign) == len(self.variables):
        solutions.append(dict(assign))
        return not find_all
    var = self._select_var(assign, domains)          # MRV + Grad-Heuristik
    for val in list(domains[var]):
        if not self._consistent(var, val, assign):
            continue
        assign[var] = val
        if propagate:
            local = {v: list(d) for v, d in domains.items()}
            local[var] = [val]
            if self._ac3(local):                     # Kantenkonsistenz
                if self._backtrack(assign, local, solutions, propagate, find_all):
                    return True
        else:
            if self._backtrack(assign, domains, solutions, propagate, find_all):
                return True
        del assign[var]
    return False

Das vollständige Skript (CSP-Klasse, AC-3, der spezialisierte Kryptarithmetik-Löser und die Grafiken) liegt in python/src/eport_figures/praxis/p_2_4_csp.py. Seine echte Ausgabe:

=== Aufgabe 2 (Blatt 6) — Mini-CSP  w,x,y,z aus {1,2,3,4} ===
    Constraints:  x > y,  y < z,  z > w
    Lösungen (Backtracking): 31   (Brute-Force-Gegenprobe: 31)
      [w=1, x=2, y=1, z=2]
      ...
      [w=3, x=4, y=3, z=4]
    besuchte Suchknoten:  ohne FC = 56,  mit AC-3 = 52
    -> MRV + Grad-Heuristik beginnt sinnvoll bei y oder z (Grad 2).

=== Aufgabe 3 (Blatt 6) — Kryptorätsel  AAL + AAL = FANG ===
    Lösung:  A=9, L=2, F=1, N=8, G=4
    Probe:   992 + 992 = 1984  (FANG = 1984)  -> stimmt
    besuchte Suchknoten:  ohne Propagierung = 26.482
    besuchte Suchknoten:  mit  Propagierung = 159
    -> Faktor 166.6x weniger Knoten.

=== Skalierung — Kryptorätsel  SEND + MORE = MONEY ===
    Lösung:  SEND=9567, MORE=1085, MONEY=10652
    Probe:   9567 + 1085 = 10652  -> stimmt
    besuchte Suchknoten:  ohne Propagierung = 2.002.687
    besuchte Suchknoten:  mit  Propagierung = 6.239
    -> Faktor 321.0x weniger Knoten.

=== Aufgabe 7 (Blatt 6) — Kantenkonsistenz herstellen:  A < B,  {0..4} ===
    AC-3 erfolgreich: True
    dom(A) nach AC-3: [0, 1, 2, 3]   (4 raus: kein größeres B möglich)
    dom(B) nach AC-3: [1, 2, 3, 4]   (0 raus: kein kleineres A möglich)

Constraint-Solving heißt, eine Lösung nicht durch Konstruktion eines Wegs zu finden, sondern durch Beschreibung ihrer Eigenschaften: Man gibt nur an, welche Bedingungen eine Lösung erfüllen muss, und überlässt das Erfüllen einem allgemeinen Löser. Alltagsbeispiele: (1) Ein Stundenplan — Variablen sind Vorlesungen, Domänen die Zeitslots, Constraints „kein Dozent doppelt”, „kein Raum doppelt”, „Pflichtmodule nicht überlappend”. (2) Eine Sitzordnung bei einer Hochzeit — Variablen sind Gäste, Domänen die Plätze, Constraints „Braut neben Bräutigam”, „Onkel Hans nicht neben Opa Karl”. Beide sind als Zuordnung unter Nebenbedingungen formuliert; das macht sie zu Constraint-Problemen. Der Unterschied zur KI-Suche liegt in der Rolle der Heuristiken: Eine A*-Heuristik wie die Luftliniendistanz ist anwendungsspezifisch — man muss das Problem kennen, um sie zu bauen. Die CSP-Heuristiken (MRV, Grad, LCV) leiten sich dagegen allein aus der Struktur der Constraints ab und funktionieren für jedes CSP gleich, ohne Domänenwissen.

Das Constraint-Netz zeigt die obige Abbildung 1: drei Kanten, die Variablen y und z als Naben mit Grad 2, w und x als Blätter mit Grad 1. Als Optimierungsheuristik wählt MRV/Grad sinnvollerweise zuerst eine der Grad-2-Variablen (y oder z), da deren Festlegung gleich zwei Constraints aktiviert und die Restdomänen der Nachbarn am stärksten beschneidet. Festlegen von y (etwa $y=1$, das kleinste mögliche, da $y$ unter zwei „Größer”-Relationen steht) macht $x>1$ und $z>1$ sofort wirksam. Das Netz ist azyklisch (ein Baum), weshalb es nach Herstellung der Kantenkonsistenz ohne Backtracking lösbar wäre — ein Spezialfall, den AC-3 hier voll ausspielt. Mein Löser findet 31 Lösungen, durch eine Brute-Force-Gegenprobe über alle $4^4 = 256$ Tupel bestätigt (siehe Ausgabe oben); die kleinste in lexikografischer Ordnung ist $[w{=}1, x{=}2, y{=}1, z{=}2]$.

Als Suchproblem (a): Zustand = partielle Buchstaben-Ziffer-Zuordnung; Anfangszustand = leere Zuordnung; Nachfolger = einem freien Buchstaben eine noch unbenutzte Ziffer geben; Zieltest = alle fünf Buchstaben belegt und $2 \cdot \overline{\mathrm{AAL}} = \overline{\mathrm{FANG}}$. Aufwand (c): Bei naiver Tiefensuche über die Buchstaben $\{A, L, F, N, G\}$ ergeben sich bis zu $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30240$ Permutationen; der Aufwand wächst exponentiell mit der Zahl verschiedener Buchstaben. Domänenwissen (d): Eine führende Ziffer ist nie $0$ (also $A \neq 0$, $F \neq 0$), und aus $\mathrm{AAL} + \mathrm{AAL}$ folgt, dass $\mathrm{FANG}$ einen Übertrag in die vierte Stelle braucht — $F = 1$. Mein Löser nutzt genau diese Struktur, indem er spaltenweise mit Übertrag rechnet statt die Zahlen erst am Ende zu prüfen.

Als CSP (f): Variablen $\{A, L, F, N, G\}$ mit Domäne $\{0, \dots, 9\}$ (für führende $A, F$: $\{1, \dots, 9\}$), dazu Übertragsvariablen $c_1, c_2, c_3 \in \{0,1\}$. Constraints: alldifferent über alle Buchstaben sowie spaltenweise

Ergebnis: Der Löser findet $A=9, L=2, F=1, N=8, G=4$, d.h. $992 + 992 = 1984$ (nachgerechnet, siehe Ausgabe). Anders als $\mathrm{SEND}+\mathrm{MORE}=\mathrm{MONEY}$ ist dieses Rätsel allerdings nicht eindeutig: Die führenden Stellen liegen fest ($A=9$, $F=1$, $N=8$), doch für die Einerspalte $2L = G + 10\,c_1$ gibt es zwei übertragsfreie Lösungen — $L=2, G=4$ (also $992+992=1984$) und $L=3, G=6$ (also $993+993=1986$). Mein Backtracking-Löser stoppt bei der ersten gefundenen Belegung, liefert also nur eine der beiden. Der Vergleich der Suchaufwände (e, g, h) ist der eigentliche Lerneffekt: Die naive Tiefensuche besucht 26.482 Knoten, der CSP-Löser mit spaltenweiser Propagierung nur 159 — Faktor 167. Beides — das Domänenwissen und die Constraint-Struktur — zusammen zu nutzen, lohnt sich also deutlich. Skalierung (i): Beim größeren $\mathrm{SEND} + \mathrm{MORE} = \mathrm{MONEY}$ klafft die Lücke noch weiter: 2.002.687 gegen 6.239 Knoten, Faktor 321 — der Vorteil der Propagierung wächst mit der Problemgröße, weil sie immer mehr Sackgassen im Keim erstickt.

Die Kante $A \to B$ verlangt zu jedem $a \in \mathrm{dom}(A)$ ein größeres $b$. Für $a = 4$ gibt es kein $b > 4$ in $\{0,\dots,4\}$ — also fliegt $4$ aus $\mathrm{dom}(A)$. Umgekehrt verlangt $B \to A$ zu jedem $b$ ein kleineres $a$; für $b = 0$ gibt es keines, also fliegt $0$ aus $\mathrm{dom}(B)$. Ergebnis: $\mathrm{dom}(A) = \{0,1,2,3\}$, $\mathrm{dom}(B) = \{1,2,3,4\}$. Mein AC-3 liefert exakt diese Domänen (siehe Ausgabe). Bei der Constraint-Propagierung wird AC-3 vor und während der Suche eingesetzt: Es entfernt unmögliche Werte, bevor man sie überhaupt probiert, und stößt bei leerer Domäne sofort ein Backtracking an.

Statt das Rätsel von Hand zu lösen, beschreibt eine CSP-Sprache nur was gilt und überlässt das Wie einem dedizierten Solver. In MiniZinc ist das Modell von AAL+AAL=FANG fast wörtlich die Aufgabenstellung — Variablen mit Domänen, all_different, die Stellenwert-Gleichung:

% AAL + AAL = FANG  als Constraint-Modell (MiniZinc)
include "globals.mzn";
var 1..9: A;  var 0..9: L;          % A führend -> != 0
var 1..9: F;  var 0..9: N;  var 0..9: G;

constraint all_different([A, L, F, N, G]);
constraint (100*A + 10*A + L) + (100*A + 10*A + L)
         = 1000*F + 100*A + 10*N + G;     % Stellenwert-Gleichung

solve satisfy;
output ["A=\(A) L=\(L) F=\(F) N=\(N) G=\(G)\n"];

Derselbe Gedanke in Choco (Java) wäre model.allDifferent(vars) plus model.scalar([…], [100,10,1,…], "=", …). Die Korrektheit des Modells belege ich mit meinem eigenen Python-Löser oben, der dieselbe Belegung $A{=}9, L{=}2, F{=}1, N{=}8, G{=}4$ ($992+992=1984$) findet. Der Gewinn der deklarativen Sprache ist Trennung von Modell und Lösung: Dasselbe Modell skaliert ohne Codeänderung zu $\mathrm{SEND}+\mathrm{MORE}=\mathrm{MONEY}$ — man tauscht nur Variablen und Gleichung.

Der Kern dieser Aufgabe ist wieder das Leitmotiv der ganzen Seite: dem Assistenten nicht glauben, sondern verifizieren. Ich habe die Antworten des Assistenten jeweils mit erschöpfender Suche gegengeprüft:

=== Aufgabe 5 (Blatt 6) — Krypträtsel mit dem KI-Assistenten ===
  (a) klassische Rätsel — Assistent-Lösung mit eigenem Löser verifiziert:
      CROSS+ROADS=DANGER:  96233 + 62513 = 158746  -> stimmt
      DONALD+GERALD=ROBERT:  526485 + 197485 = 723970  -> stimmt
  (b) selbst erzeugtes Rätsel HAUS + HAUS = STADT — auf Eindeutigkeit geprüft:
      6041 + 6041 = 12082  (eindeutig: 1 Lösung)
  (c) Multiplikationsrätsel  X*Y = ZY  und  Z + B = Y:
      X=3, Y=5, Z=1, B=4:  3*5=15 (ZY), 1+4=5
      X=7, Y=5, Z=3, B=2:  7*5=35 (ZY), 3+2=5
      X=9, Y=5, Z=4, B=1:  9*5=45 (ZY), 4+1=5
      -> 3 gültige Lösungen — das Rätsel ist NICHT eindeutig.

(a) Lösen. Der Assistent löst die großen Additionsrätsel $\mathrm{SEND}+\mathrm{MORE}=\mathrm{MONEY}$, $\mathrm{CROSS}+\mathrm{ROADS}=\mathrm{DANGER}$ und $\mathrm{DONALD}+\mathrm{GERALD}=\mathrm{ROBERT}$ souverän — sie sind klassisch und stehen vielfach in den Trainingsdaten. Meine Verifikation bestätigt alle drei. (b) Erzeugen. Ich habe den Assistenten gebeten, ein neues Rätsel im selben Stil zu erfinden; als Ergebnis prüfe ich $\mathrm{HAUS}+\mathrm{HAUS}=\mathrm{STADT}$ und stelle per erschöpfender Suche fest, dass es genau eine Lösung hat ($6041+6041=12082$) — also ein wohlgeformtes Rätsel. Das ist nicht selbstverständlich: Viele spontan erzeugte Kandidaten (etwa $\mathrm{EINS}+\mathrm{EINS}=\mathrm{ZWEI}$) haben mehrere Lösungen und sind als Rätsel untauglich; ohne Verifikation merkt man das nicht. (c) Korrigieren. Das Multiplikationsrätsel $X\cdot Y=ZY,\ Z+B=Y$ ist der lehrreichste Fall: Es hat drei Lösungen (alle mit $Y=5$). Ein LLM liefert typischerweise nur eine und behauptet implizit Eindeutigkeit — genau hier greift der vom Blatt geforderte Korrekturschritt: Man weist auf die fehlende Eindeutigkeit hin und stellt das Rätsel zur Kontrolle mit anderen Buchstaben oder einer schärferen Zusatzbedingung erneut. Der CSP-Löser ist dabei das Korrektiv, das der LLM-Antwort fehlt.

• Personaleinsatz-/Schichtplanung (z.B. Krankenhaus). Typisches CSP: Nurse Rostering — Variablen sind die Schichten je Pflegekraft und Tag, Domänen die möglichen Dienste (Früh/Spät/Nacht/frei), Constraints u.a. „Mindestbesetzung je Schicht”, „keine Nacht direkt vor Frühdienst”, „maximale Wochenstunden”, „Urlaubswünsche”. Ein klassisches, hart NP-schweres Zuordnungsproblem unter vielen harten und weichen Bedingungen.
• Produktkonfiguration (z.B. Auto- oder PC-Konfigurator). Typisches CSP: Ein Konfigurationsproblem — Variablen sind die wählbaren Komponenten (Motor, Felgen, Software-Pakete), Domänen die Varianten, Constraints kodieren technische Kompatibilität und Abhängigkeiten („Anhängerkupplung erfordert verstärktes Fahrwerk”, „Paket A schließt Paket B aus”). Der Solver hält die Konfiguration während der Auswahl stets konsistent (interaktive Propagierung).
• Mobilfunk-/Funkfrequenzplanung. Typisches CSP: Frequency Assignment — Variablen sind die Sender, Domänen die verfügbaren Kanäle/Frequenzen, Constraints verlangen, dass sich räumlich benachbarte Sender nicht stören (Mindestabstand der Frequenzen). Das ist im Kern eine verallgemeinerte Graphfärbung — derselbe CSP-Typ wie die Landkartenfärbung aus den Kernkonzepten, nur mit Anwendungsdruck und Optimierungsziel.

Querbezüge#

• 2.2 (Suchverfahren): Backtracking ist die Tiefensuche (DFS) jenes Themas, nur mit einem Konsistenztest nach jeder Belegung. Der ganze Unterschied — und die ganze Beschleunigung — entsteht daraus, dass das CSP den Zustand nicht mehr als Blackbox behandelt, sondern seine Variablenstruktur freilegt.
• 2.3 (Spielbäume): α-β-Pruning und Constraint-Propagierung verfolgen dasselbe Ziel mit verwandten Mitteln — Teilbäume gar nicht erst zu betreten, von denen feststeht, dass sie nichts beitragen. Beide messen ihren Erfolg in „nicht expandierten Knoten”.
• 8.1 (Logik & SAT): Neuere Constraint-Löser übersetzen das CSP in eine aussagenlogische Formel und lassen einen SAT-Solver darauf los; AC-3 ist dabei ein Verwandter der Unit Propagation im DPLL-Algorithmus. Boolesche Constraints sind der direkte Brückenkopf zur symbolischen KI.
• Theoretische Informatik: Die Erfüllbarkeit allgemeiner CSPs ist NP-vollständig — Graphfärbung und 3-SAT, beides CSP-Spezialfälle, gehören zu den kanonischen NP-vollständigen Problemen. Heuristiken und Propagierung ändern nichts an der Worst-Case-Komplexität, machen aber die typischen Fälle praktisch lösbar. Der azyklische Spezialfall (A2) ist sogar in Polynomzeit lösbar — ein Beispiel dafür, wie Problemstruktur die Komplexität senkt.
• Operations Research: Die Lineare Programmierung ist der effizient lösbare Spezialfall linearer Constraints; weiche Constraints mit Kostenfunktion machen aus dem CSP eine Optimierungsaufgabe (Constraint Optimization), wie sie etwa Google OR-Tools für Scheduling und Bin-Packing löst.

Quellen#

• Foliensatz _240_Constraints.pdf — Grundlage für die Begriffe (CSP, Backtracking, Forward Checking, Kantenkonsistenz) und die Heuristiken. Besonders der Anhang zum AC-3-Algorithmus mit arc-reduce und dem Beispielnetz $A,B,C$ über $\{1,2,3,4\}$ war die Vorlage für meine Implementierung; die Sackgassen- Statistik (1371 vs. 3 beim Vergleich der beiden Variablen-Reihenfolgen) habe ich als Motivation übernommen, aber nicht nachgerechnet.
• Übungsblatt ki_ueb240_CSP.pdf (Blatt 6) — die hier gelösten Aufgaben 1, 2, 3, 4, 5, 6 und 7. Die Kryptorätsel-Aufgabe verlangt explizit den Vergleich von Suchaufwand mit und ohne Strukturwissen, was meine Praxis direkt umsetzt; die LLM-Krypträtsel (A5) habe ich jeweils mit erschöpfender Python-Suche gegengeprüft.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 6 („Constraint Satisfaction Problems”) — als Referenz für die saubere Definition von Kantenkonsistenz und die $\mathcal{O}(n^2 d^3)$-Schranke von AC-3 herangezogen.
• MiniZinc / Choco-Solver — die in Blatt 6 (A4) empfohlenen CSP-Sprachen. Das in A4 gezeigte MiniZinc-Modell von $\mathrm{AAL}+\mathrm{AAL}=\mathrm{FANG}$ ist eine deklarative Formulierung; ihre Korrektheit ist mit dem eigenen Python-Löser belegt (dieselbe Belegung $992+992=1984$).