Constraint-Programmierung: Probleme durch Bedingungen lösen

Constraint-Programmierung (Constraint Programming, kurz CP) ist ein deklarativer Lösungsansatz für schwierige Kombinatorik-Probleme: Statt einen Algorithmus Schritt für Schritt vorzugeben, beschreibt man Variablen, Wertebereiche und Bedingungen – und ein generischer Solver sucht die Lösung. Die Anwendung sagt dem Rechner, was gelten soll, nicht wie er es erreicht. Damit ist die Constraint-Programmierung eine besondere Form der deklarativen Programmierung.

Das Grundmodell: CSP

Ein Constraint-Satisfaction-Problem (CSP) besteht aus drei Teilen:

Variablen – zum Beispiel X, Y, Z für die Ziffern einer Sudoku-Zelle.
Wertebereiche (Domänen) – die erlaubten Werte, etwa 1..9.
Constraints – Bedingungen über Kombinationen, etwa „alle Ziffern einer Zeile sind paarweise verschieden“.

Eine Lösung ist eine Belegung aller Variablen mit Werten aus ihren Domänen, die sämtliche Constraints erfüllt. Bekannte Beispiele sind Sudoku, Stundenplan- und Turnierplanung, Schichtplanung, Maschinenbelegung, Routenplanung und das Färben von Landkarten.

Zwei Arbeitstechniken

Moderne CP-Solver kombinieren typischerweise zwei Verfahren:

Constraint-Propagation: Die Solver ziehen aus den Constraints Schlüsse und schränken die Domänen ein, bevor sie raten. Ein Klassiker ist der AC-3-Algorithmus (Alan Mackworth, 1977), der Bogen-Konsistenz (Arc Consistency) herstellt: Ist für einen Wert von X kein passender Wert von Y mehr möglich, wird er aus der Domäne entfernt – ohne dass ein Wert ausprobiert wurde.
Backtracking-Suche: Reicht die Propagation nicht, belegt der Solver eine Variable probeweise und geht bei Widersprüchen zurück. Der Suchbaum wird durch Heuristiken wie „Minimum Remaining Value“ (zuerst die Variable mit den wenigsten Möglichkeiten) stark beschnitten.

Dieses Zusammenspiel unterscheidet CP von reinem Backtracking: Propagierung erledigt den logischen Teil, die Suche nur den Rest.

Werkzeuge und Abgrenzung

CP-Solver und Bibliotheken: Choco (Java), Google OR-Tools (CP-SAT-Solver), MiniZinc (modellbasierte Zwischensprache), SWI-Prolog mit CLP(FD) – der Brückenschlag zur logischen Programmierung. Verwandte, aber andere Ansätze: dynamische Programmierung (optimales Zerlegen in Teilprobleme) und ganzzahlige Optimierung (numerische Zielfunktionen statt reiner Zulässigkeit).