Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen

Variablen, Domänen und Constraints, der Constraint-Graph, Backtracking, die Heuristiken MRV und LCV, Forward Checking, AC-3 und Min-Conflicts — am Färben der tschechischen Regionen, an Sudoku und an acht Damen.

15 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 23 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Ein Stundenplan, in dem kein Lehrer zwei Klassen gleichzeitig unterrichtet. Sudoku. Die Platzierung von Bauteilen auf einer Platine, Schichten im Krankenhaus, die Zuteilung von Flugzeugen zu Gates. All diese Aufgaben haben gemeinsam, dass wir keinen Weg suchen, sondern eine Zuweisung: Jeder Variable einen Wert geben, sodass alle Regeln auf einmal gelten. Eine solche Aufgabe heißt Constraint-Satisfaction-Problem, und im Unterschied zur allgemeinen Suche hat sie einen großen Vorteil — die Regeln sind sichtbar, sodass der Algorithmus aus ihnen schließen kann, statt nur zu probieren.

Er baut auf den Teilen Zustandsraumsuche und Graphen und Bäume auf.

1. Was ein Constraint-Satisfaction-Problem ist

Definition — CSP

Ein Constraint-Satisfaction-Problem (constraint satisfaction problem, CSP) ist ein Tripel (X, D, C), wobei

• X = {X₁, …, X_n} die Menge der Variablen ist,
• D = {D₁, …, D_n}, wobei D_i die Domäne ist — die Menge der Werte, die X_i annehmen darf,
• C die Menge der Constraints ist. Jeder Constraint ist ein Paar (Geltungsbereich, Relation): Der Geltungsbereich ist eine Liste von Variablen, die Relation gibt an, welche Kombinationen ihrer Werte erlaubt sind.

Ein Constraint mit zwei Variablen im Geltungsbereich ist binär, zum Beispiel X₁ ≠ X₂.

Definition — Zuweisung und Lösung

Eine Zuweisung gibt einigen Variablen einen Wert aus ihrer Domäne. Sie ist konsistent, wenn sie keinen Constraint verletzt, und vollständig, wenn jede Variable einen Wert hat.

Eine Lösung eines CSP ist eine vollständige konsistente Zuweisung.

Warum das nicht als gewöhnliche Suche auffassen? Das ginge — der Zustand ist eine angefangene Zuweisung, die Aktion ist „Gib der nächsten Variable einen Wert“. Nur würde die Suche den Zustand als Blackbox betrachten. Ein CSP sieht in die Box hinein: Es weiß, welche Regeln gelten und welche Variablen sie betreffen. Darauf beruhen alle Tricks in diesem Teil.

2. Der Constraint-Graph: eine Karte von Regionen färben

Eine klassische Aufgabe: eine Karte so färben, dass keine zwei benachbarten Staaten dieselbe Farbe haben. Wir nehmen die vierzehn Regionen Tschechiens. Die Variablen sind die Regionen, die Domäne ist ein Satz Farben, und für jede gemeinsame Grenze gibt es den Constraint „verschiedene Farben“.

Definition — Constraint-Graph

Der Constraint-Graph eines binären CSP hat die Variablen als Knoten und eine Kante zwischen X_i und X_j genau dann, wenn ein Constraint sie verbindet.

Mit vier Farben geht es glatt. Mit dreien geht es überhaupt nicht — und der Graph zeigt, warum. Die Mittelböhmische Region grenzt an Prag und an sieben Regionen, die um sie herum einen geschlossenen Ring bilden. Ein Ring mit einer ungeraden Zahl von Knoten braucht schon für sich allein drei Farben (zwei müssten sich regelmäßig abwechseln, und das geht bei einer ungeraden Zahl nicht auf). Die Mittelböhmische Region grenzt an alle sieben, also muss für sie eine vierte Farbe übrig bleiben:

Dass vier Farben für jede Karte genügen, ist der berühmte Vierfarbensatz. Bewiesen haben ihn Appel und Haken im Jahr 1976 — als ersten großen mathematischen Satz mithilfe eines Computers, der fast zweitausend Fälle überprüfte.

3. Backtracking

Definition — Backtracking

Backtracking ist eine Tiefensuche, die in jedem Schritt einer weiteren Variable einen Wert zuweist. Einen Wert, der einen Constraint mit bereits zugewiesenen Variablen verletzt, probiert sie gar nicht erst. Bleibt für eine Variable kein Wert übrig, kehrt sie zur vorherigen Variable zurück und probiert deren nächsten Wert.

Im schlimmsten Fall durchläuft sie O(dⁿ) Zuweisungen, wobei d die Größe der Domäne und n die Zahl der Variablen ist. Das allgemeine CSP ist NP-schwer, im schlimmsten Fall können wir es also nicht besser.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # alles hat einen Wert: Lösung
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # Sackgasse: zurück
    return None

Bei den Regionen mit vier Farben macht Backtracking 14 Zuweisungen, eine pro Region, und kehrt kein einziges Mal zurück. Mit drei Farben muss es beweisen, dass es keine Lösung gibt — und das heißt, alles auszuprobieren: 93 Zuweisungen, bevor es aufgibt.

4. Welche Variable und welcher Wert

Das Gerüst des Backtrackings lässt zwei Fragen offen: welche Variable als nächste dran ist und in welcher Reihenfolge ihre Werte probiert werden. Auf die Antworten kommt es mehr an, als man denken würde.

Definition — MRV, Grad, LCV

MRV (minimum remaining values): Wähle die Variable mit der kleinsten Zahl von Werten, die noch nicht im Konflikt mit der Zuweisung stehen.

Gradheuristik: Wähle bei Gleichstand die Variable, die die meisten Constraints mit noch nicht zugewiesenen Variablen hat.

LCV (least constraining value): Probiere die Werte einer Variable beginnend mit dem, der den Nachbarn die wenigsten Möglichkeiten streicht.

Bei drei Farben auf den Regionen senkt MRV zusammen mit dem Forward Checking aus dem nächsten Kapitel die Zahl der Zuweisungen von 93 auf 45 — es beginnt bei der Region, der die wenigsten Farben bleiben, und findet den Widerspruch doppelt so schnell.

5. Forward Checking

Definition — Forward Checking

Gehe nach der Zuweisung X_i = v jede nicht zugewiesene Variable X_j durch, die mit X_i durch einen Constraint verbunden ist, und entferne aus D_j die mit v unverträglichen Werte. Bleibt eine Domäne leer, nimm die Zuweisung sofort zurück.

Der Unterschied zeigt sich am Sudoku unten. Einfaches Backtracking über die Felder zeilenweise braucht über 14 Millionen Zuweisungen. Mit Forward Checking sind es 11 400. Und wenn wir MRV hinzunehmen, fällt es auf 81 — 30 vorgegebene Zahlen und 51 ergänzte, ohne ein einziges Zurückgehen.

6. Kantenkonsistenz und AC-3

Forward Checking schaut nur einen Schritt weiter: auf die Nachbarn der Variable, die wir gerade zugewiesen haben. Es geht gründlicher — auch zwischen Variablen streichen, die noch keinen Wert haben.

Definition — Kantenkonsistenz

Eine Variable X_i ist kantenkonsistent bezüglich X_j, wenn es für jeden Wert x ∈ D_i ein y ∈ D_j gibt, sodass das Paar (x, y) den Constraint zwischen ihnen erfüllt. Ein CSP ist kantenkonsistent, wenn das für jede gerichtete Kante (X_i, X_j) des Constraint-Graphen gilt.

Algorithmus — AC-3

1. Lege alle gerichteten Kanten (X_i, X_j) in die Warteschlange.
2. Nimm eine Kante aus der Warteschlange und entferne aus D_i jeden Wert, der in D_j keinen Partner hat.
3. Ist D_i kleiner geworden, lege alle Kanten (X_k, X_i) für die Nachbarn X_k ≠ X_j wieder in die Warteschlange — ihre Werte könnten gerade ihren Partner verloren haben. Ist D_i leer, hat das CSP keine Lösung.
4. Wiederhole, bis die Warteschlange leer ist.

Für c binäre Constraints und Domänen der Größe höchstens d braucht AC-3 O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # leere Domäne: es gibt keine Lösung
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Sudoku: Propagierung in der Praxis

Sudoku ist ein CSP wie aus dem Lehrbuch: 81 Variablen, Domänen {1, …, 9} und der Constraint „verschiedene Werte“ für jedes Paar von Feldern in derselben Zeile, Spalte oder demselben 3 × 3-Block. Jedes Feld hat also 20 Nachbarn im Constraint-Graphen.

Lassen wir auf eine Vorgabe mit 30 Zahlen AC-3 allein los, ohne eine einzige Zuweisung aufs Geratewohl. Es streicht 408 Werte — und jedem der 51 leeren Felder bleibt genau einer. Das Sudoku ist durch reines Nachdenken gelöst:

Bei leichten Sudokus läuft es so; bei schwereren bleibt die Propagierung irgendwo stecken, und die Suche übernimmt — Backtracking, das nach jeder Zuweisung erneut die Propagierung startet. Diese Kombination (Aufrechterhalten der Kantenkonsistenz, MAC) ist die Grundlage der meisten echten Solver. Zum Vergleich auf derselben Vorgabe:

Von vierzehn Millionen auf null. Rohe Gewalt und kluges Nachdenken lösen dieselbe Aufgabe — nur eine von beiden liest die Regeln.

8. Lokale Suche: Min-Conflicts

Eine völlig andere Strategie: die Lösung nicht Stück für Stück aufbauen, sondern mit einer vollständigen Zuweisung beginnen, die eine Menge Constraints verletzt, und sie schrittweise reparieren. Es ist die lokale Suche aus dem Teil über die Suche, nur ist die Zielfunktion die Zahl der verletzten Constraints.

Algorithmus — Min-Conflicts

1. Beginne mit einer zufälligen vollständigen Zuweisung.
2. Solange ein Constraint nicht gilt: Wähle zufällig eine Variable im Konflikt und gib ihr den Wert, mit dem sie die wenigsten Constraints verletzt (bei Gleichstand zufällig).

Der klassische Test ist das n-Damen-Problem: n Schachdamen so auf einem n × n-Schachbrett aufstellen, dass sich keine zwei bedrohen. Die Variable ist die Zeile der Dame in jeder Spalte. Für acht Damen begann unser Lauf mit sechs sich bedrohenden Paaren und endete nach 8 Schritten:

Beachte die mittleren Schritte: Die Zahl der Konflikte bleibt vier Schritte lang bei eins — der Algorithmus verschiebt die Damen „seitwärts“ über ein Plateau, bis er einen Zug findet, der den Widerspruch beseitigt. Überraschend ist, wie gut das skaliert: Eine Million Damen löst Min-Conflicts im Durchschnitt in ungefähr fünfzig Schritten. Mit demselben Verfahren wurden die Beobachtungen des Hubble-Weltraumteleskops geplant.

9. Constraints in der Praxis

• Stundenpläne und Planung. Schulstundenpläne, Schichten, die Zuteilung von Räumen und auch Produktionspläne werden als Variablen, Domänen und Constraints formuliert. Solver wie Google OR-Tools kombinieren Propagierung, Suche und lokale Verbesserung.
• SAT-Solver lösen CSPs, bei denen jede Variable wahr/falsch ist. Sie verifizieren Chipentwürfe, suchen Fehler in Software, und Paketmanager (zum Beispiel unter Linux) stellen mit ihnen Versionen von Bibliotheken zusammen, die miteinander funktionieren.
• Compiler verteilen die Variablen eines Programms durch Graphfärbung auf die Register des Prozessors: Zwei Variablen, die gleichzeitig leben, dürfen sich kein Register teilen — genau wie benachbarte Regionen keine Farbe.
• Konfiguratoren in Onlineshops und in der Produktion achten darauf, dass die gewählten Bauteile zusammenpassen.
• KI-Agenten und Sprachmodelle glänzen bei CSPs oft nicht: Für ein Sudoku oder einen Stundenplan eignet sich ein Solver zuverlässiger. Ein guter Agent denkt die Aufgabe deshalb nicht „im Kopf“ durch — er übersetzt sie in Variablen und Constraints und ruft dafür ein Werkzeug auf.

10. Zusammenfassung

• Ein CSP ist ein Tripel (X, D, C): Variablen, Domänen und Constraints. Eine Lösung ist eine vollständige Zuweisung, die keinen Constraint verletzt.
• Backtracking weist die Variablen eine nach der anderen zu und kehrt aus Sackgassen zurück; im schlimmsten Fall ist es exponentiell.
• Die Heuristiken MRV und LCV wählen die schwierigste Variable und den entgegenkommendsten Wert; Forward Checking deckt eine Sackgasse einen Schritt früher auf.
• AC-3 propagiert Streichungen durch den Constraint-Graphen, bis jeder Wert einen Partner hat; ein leichtes Sudoku löst es ganz ohne Suche.
• Min-Conflicts repariert eine vollständige Zuweisung und schafft auch riesige Aufgaben wie eine Million Damen.

Willst du es selbst ausprobieren? Lass einen KI-Agenten einen Sudoku-Solver mit Backtracking schreiben und füge dann Forward Checking, MRV und AC-3 hinzu — und zähle, wie viele Zuweisungen wegfallen.

Siehst du das anders? Schreib an support@coden-app.com.