# Constraint satisfaction

Expose both satisfiable assignments and complete impossibility arguments for finite variable domains.

## Definitions

- **Constraint**: A relation restricting allowed variable assignments.
- **Graph coloring**: Adjacent vertices must receive different colors.
- **Solution space**: Every assignment satisfying all declared constraints.

## Acceptance procedure

1. Enumerate one color value for each vertex.
2. Check every edge’s unequal-color constraint.
3. Count the complete solution space.
4. Validate a coloring witness, or require enumeration evidence when no model exists.

## Complexity

k colors on n vertices produce kⁿ assignments. Color-label permutations can create symmetric solutions.

## Common failure

Failing to find a solution is not equivalent to proving there is none.

## Extensions

Add symmetry reduction and checked propagation or conflict explanations.

## Instances

- KL-FCS-046: A triangle cannot use two colors — Satisfiable: no; Solution count: 0
- KL-FCS-047: A four-cycle admits two colors — Satisfiable: yes; Solution count: 2
- KL-FCS-048: Four pairwise adjacent vertices need more colors — Satisfiable: no; Solution count: 0

## References

- https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/download/