Constraint-Satisfaction

Das CSP-Problem

Gegeben

• Begrenztes 11×10 Raster (110 Positionen)

• Menge von Wörtern W = {ES, IST, FÜNF, ZEHN, ...}

• Regeln R für Platzierung

Gesucht

• Zuweisung Position(w) für jedes Wort w ∈ W

• So dass alle Regeln r ∈ R erfüllt sind

Constraints C1: Eindeutigkeit

• Jede Position darf nur einen Buchstaben enthalten

• ∀ p: |{w | p ∈ Position(w)}| ≤ 1

C2: Ordnung

• Position(FÜNF_Minuten) < Position(HALB) < Position(FÜNF_Stunde)

• Position(ES) < Position(IST) < ... < Position(UHR)

C3: Nachbarschaft

• ∀ p: Buchstabe(p) ≠ Buchstabe(p+1) (horizontal)

• ∀ p: Buchstabe(p) ≠ Buchstabe(p+11) (vertikal)

C4: Vollständigkeit

• ∀ w ∈ W_erforderlich: Position(w) existiert

Lösungsstrategien

Greedy-Ansatz: Wörter nacheinander platzieren Backtracking: Bei Konflikt zurückgehen Constraint-Propagation: Unmögliche Positionen frühzeitig ausschließen Heuristiken: Wichtige Wörter zuerst platzieren

Visuelle Feedback-Logik