Notations
- Variable V - smth that can receive assignments
- Values X - smth can be assigned
- Domain D - set of values a variable can take
- Constraint c - what limits the domains of variables
For each DFS assignment:
For each variable v considered:
For each x_i in D_i:
For each c(x_i, x_j), x_j in D_j
If there is no x_j <=> C(x_i, x_j)
Remove x_i from D_i
If D_i is empty:
backtrack
Domain reduction
What to consider:
- nothing
- neighbours
- variables with reduced domain (led(D) = 1)
- everything
TIP
Start with the most constrained variables