## Domain Reduction Algorithm

### Vocabulary

**Variable**: something that can have an assignment*v***Value**: something that can be assigned*x***Domain**: set of all different values*d***Constraint**: limit on variable values*c*

With a depth-first search, the **domain reduction algorithm** goes back up one node when it is unable to comply with a constraint. It reduces the domain of available variables at node *n-1* to make sure it will have an unused variable in the next node *n*.

By considering more variables (propagating to neighboring states in the US map coloring example), the **domain can be reduced to a single value** at a certain node.

### Solving the problem faster

By working on the **most constraints nodes first**, the algorithm doesn’t have to work back up as much as if it starts with least constraints first.

Obviously, the main constraint of using only a small number of values (colors in the example) is the most limiting one. Being able to **increase the number of values** can drastically simplify the problem.

In case of **uncertainty** on the exact number of values, find a **range of values** that solve the problem (such as in the airplane assignment example).

## Resources allocations

- Used most constraints first
- Propagate through domain reduced to single algorithm
- In the absence of definite result, find a narrow range of max values where it doesn’t work, and min values where it does