50 Variety of CSPs

Variables

• Finite domains (discrete)
• Infinite domains (discrete or continuous), e.g., variable involving time.

Constraints

• Unary, binary and high order constraints; i.e., how many variables involved in a constraint.

CSPs are difficult search problems

• If a CSP has $n$ variables, the size of each domain is $d$, then there are $O(d^n)$complete assignments.
• For the previous Sudoku problem, there are $9^{51}$ complete assignments .