All Different

• Suppose Dx = {2,3} = Dy, Dz = {1,2,3}

• All the constraints x?y, y?z, z?x are all arc consistent

  • e.g. x=2 supports the value z = 3

• the single ternary constraint AllDifferent(x,y,z) is not!

  • We must set z = 1

• Generalised Arc Consistency applies to n-ary constraints (but complicated and expensive)

• A special purpose algorithm exists for All-Different to establish GAC in efficient time

• Special purpose propagation algorithms are vital

Previous slide

Next slide

Back to first slide

View graphic version