Special kinds of Consistency

• Some kinds of constraint lend themselves to special kinds of arc-consistency

• Consider the all-different constraint

  • the named variables must all take different values
  • not a binary constraint
  • can be expressed as n(n-1)/2 not-equals constraints

• We can apply (e.g.) AC3 as usual

• But there is a much better option

Previous slide

Next slide

Back to first slide

View graphic version