Erklärung CSP

Aufgabe
Wenn das Rätsel nach einer Zuordnung von Werten zu bestimmten Variablen fragt, unter bestimmten Einschränkungen / Bedingungen, dann nennt man das ein Constraint Satisfaction Problem (CSP). CSPs löst man wie folgt: - Notiere für jede Variable den möglichen Wertebereich - Wende folgende Schritte so lange wie möglich an: (1) Nutze die Nebenbedingungen (Constraints) aus, um den Wertebereich systematisch einzuschränken. (2) Fixiere Variablen, die nur noch einen möglichen Wert haben. - Wenn sonst nichts hilft: Belege eine Variable mit einem Wert und versuche wieder die Schritte oben; falls keine Lösung erzielt wird (ein Widerspruch in den Constraints auftaucht) kann dieser Wert ausgeschlossen werden ("Brute-Force mit Backtracking").

Wenn das Rätsel nach einer Zuordnung von Werten zu bestimmten Variablen fragt, unter bestimmten Einschränkungen / Bedingungen, dann nennt man das ein Constraint Satisfaction Problem (CSP).

CSPs löst man wie folgt:
- Notiere für jede Variable den möglichen Wertebereich
- Wende folgende Schritte so lange wie möglich an:
(1) Nutze die Nebenbedingungen (Constraints) aus, um den Wertebereich systematisch einzuschränken.
(2) Fixiere Variablen, die nur noch einen möglichen Wert haben.
- Wenn sonst nichts hilft: Belege eine Variable mit einem Wert und versuche wieder die Schritte oben; falls keine Lösung erzielt wird (ein Widerspruch in den Constraints auftaucht) kann dieser Wert ausgeschlossen werden ("Brute-Force mit Backtracking").

Aufgabe

Lösung