Cs188AI Wiki

General Info[]


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.


  1. Start will all arcs in a queue of arcs
  2. Pick an arc from the queue and check it for arc consistency
  3. If the arc was not consistent, add all of the arcs that were pointing to the tail of the inconsistent arc



  • Enforcing arc consistency reduces the amount of backtracking that needs to be done because we can detect inevitable failures earlier


  • Calculating and enforcing arc consistency may take a while computationally. It is similar to the idea of A Star Search where calculating heuristics may be expensive but it reduces the amount of nodes that need to be explored in search.