Aka. CSP.
Defined by a set of variables, their domains, and constraints. Solution to a CSP is a complete and consistent assignment.
CSPs are useful because they:
- provides a uniform structure for diverse problems.
- enables general-purpose solvers without problem-specific logic.
- allows early elimination of inconsistent states, reducing the search space.
Terminology
Section titled “Terminology”Variable
Section titled “Variable”Can either be discrete or continuous.
Domain
Section titled “Domain”Possible values for a given variable. Can either be finite or infinite.
Defined by values assigned to all or some variables.
Constraint
Section titled “Constraint”Defines allowable combinations of values for a subset of variables. Can either be:
- Unary: Single variable (e.g., SA ≠ green).
- Binary: Pairs of variables (e.g., SA ≠ WA).
- Global: Multiple variables involved together.
Assignment
Section titled “Assignment”Gives values to some or all variables.
Complete Assignment
Section titled “Complete Assignment”Assigns all variables.
Consistent Assignment
Section titled “Consistent Assignment”Aka. legal assignment. An assignment that satisfies all constraints.
Local Search for CSP
Section titled “Local Search for CSP”Effective for large CSPs like N-Queens, often reaching solutions quickly.
Approach:
- Start with a random complete assignment.
- Choose a conflicted variable randomly.
- Reassign its value to minimize conflicts.
Min-Conflicts Heuristic:
- Select the value causing the fewest violations.
- Used in hill climbing or simulated annealing variants.