Global Constraint Catalog: Calldifferent

5.18. alldifferent_modulo

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Constraint

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝙼)$

Synonyms

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏_𝚖𝚘𝚍𝚞𝚕𝚘$ , $𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ .

Arguments

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙼$	$𝚒𝚗𝚝$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝙼 > 0

𝙼 \geq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

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 𝙼 \neq v \mod 𝙼$ can be swapped.

Arg. properties

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	4	12	48	240	1440	10080	80640

Number of solutions for $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ : domains $0 . . n$

ctrs/alldifferent_modulo-1-tikz

ctrs/alldifferent_modulo-2-tikz

Length (

n

)

Total

240

1440

10080

80640

Parameter

value

240

1440

10080

80640

Solution count for $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ : domains $0 . . n$

ctrs/alldifferent_modulo-3-tikz

ctrs/alldifferent_modulo-4-tikz

See also

implies: $𝚜𝚘𝚏𝚝_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚟𝚊𝚛$ .

specialisation: $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \mod 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

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

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: one_succ.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 \mod 𝙼 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \mod 𝙼

Graph property(ies)

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

\leq 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.18.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 components of the final graph.

Figure 5.18.1. Initial and final graph of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint


(a)	(b)

Automaton: Figure 5.18.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.18.2. Automaton of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.18. alldifferent_modulo

Figure 5.18.1. Initial and final graph of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint

Figure 5.18.2. Automaton of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.18. alldifferent_modulo

Figure 5.18.1. Initial and final graph of the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘 constraint

Figure 5.18.2. Automaton of the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘 constraint

Figure 5.18.1. Initial and final graph of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint

Figure 5.18.2. Automaton of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint