What makes CSP problems hard?
Asignments to individual variables that seem locally consistent are often globally infeasible, causing costly backtracking.
The difficulty of a CSP/SAT problem depends on
- Number of variables (propositions)
- Number of constraints (clauses)
- Degree of local consistency
#constraints / # Variables