5.11. alldifferent_modulo

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,𝙼)

Synonyms

πšŠπš•πš•πšπš’πšπš_πš–πš˜πšπšžπš•πš˜, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš–πš˜πšπšžπš•πš˜.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Όπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
𝙼>0
𝙼β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
Purpose

Enforce all variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to have a distinct rest when divided by 𝙼.

Example
(25,1,14,3,5)

The equivalence classes associated with values 25, 1, 14 and 3 are respectively equal to 25 mod 5=0, 1 mod 5=1, 14 mod 5=4 and 3 mod 5=3. Since they are distinct the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜ constraint holds.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
𝙼>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • A value u of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be renamed to any value v such that v is congruent to u modulo 𝙼.

  • Two distinct values u and v of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› such that u mod 𝙼≠v mod 𝙼 can be swapped.

See also

specialisation: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

characteristic of a constraint: modulo, all different, automaton, automaton with array of counters.

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: one_succ.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› mod 𝙼=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš› mod 𝙼
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀1

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Graph model

Exploit the same model used for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint. We replace the binary equality constraint by another equivalence relation depicted by the arc constraint. We generate a clique with a binary equality modulo 𝙼 constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed 1.

PartsΒ (A) andΒ (B) of FigureΒ 5.11.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph.

Figure 5.11.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/alldifferent_moduloActrs/alldifferent_moduloB
(a) (b)
Automaton

FigureΒ 5.11.2 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜ constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 1. The automaton counts for each equivalence class the number of used values and finally imposes that each equivalence class is used at most one time.

Figure 5.11.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜ constraint
ctrs/alldifferent_modulo1