Establishing Arc Consistency
If we consider every constraint and full propagation, there are only two possibilities:
- the final problem will be arc-consistent
- every value in every domain is supported by some other value in every constraint
- we have established arc consistency
- at some point some variable will have an empty domain
- no value can be given to that variable
- the problem is insoluble due to arc consistency
- we have seen a domain wipe out
A number of algorithms can be used to establish AC