Arc consistency is maintained when for every x in the tail variable's domain, there is some y in the head variable's domain such that the pair of values don't cause a constraint violation.
- Start will all arcs in a queue of arcs
- Pick an arc from the queue and check it for arc consistency
- If the arc was not consistent, add all of the arcs that were pointing to the tail of the inconsistent arc
- Arc consistency runs inside a backtracking search, after each assignment
- Arc consistency is really just a special case of k consistency where
- Enforcing arc consistency reduces the amount of backtracking that needs to be done because we can detect inevitable failures earlier