Search code examples
artificial-intelligenceconstraint-programmingconstraint-satisfaction

Example of arc consistency does not imply satisfiability

I've read that arc consistency does not imply satisfiability. The provided example was

X in D ∧ Y in D ∧ X ≠ Y ∧ X = Y

for domains D with more than one value.

My understanding is that for each of the possible values of X (from D) there are values of Y (from the same D) such that the above constraint is satisfied.

Could someone please give me an example of this?

Solution

  • I've found this explanation and I think I understood my mistake.

    Arc consistency it's about atomic constraints

    A constraint is consistent if a subproblem, containing only that constraint and its variables and their domains:

    • has a solution
    • there is a solution when an arbitrary variable gets an arbitrary value from its domain

    So in my case the atomic constraints X ≠ Y and X = Y are arc consistent, where X in D ∧ Y in D and D has more than one value.