## 5.17. alldifferent_interval

 DESCRIPTION LINKS GRAPH AUTOMATON
Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$.

Arguments
 $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}$ $\mathrm{\pi \pi \pi }$
Restrictions
 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}>0$
Purpose

Enforce all variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ to belong to distinct intervals. The intervals are defined by $\left[\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}Β·k,\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}Β·k+\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}-1\right]$ where $k$ is an integer.

Example
$\left(β©2,4,10βͺ,3\right)$

In the example, the second argument $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}=3$ defines the following family of intervals $\left[3Β·k,3Β·k+2\right]$, where $k$ is an integer. Since the three variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ take values that are respectively located within the three following distinct intervals $\left[0,2\right]$, $\left[3,5\right]$ and $\left[9,11\right]$, the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds.

All solutions

FigureΒ 5.17.1 gives all solutions to the following non ground instance of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{0}$ constraint: ${V}_{1}\beta \left[0,7\right]$, ${V}_{2}\beta \left[1,2\right]$, ${V}_{3}\beta \left[2,3\right]$, ${V}_{4}\beta \left[0,9\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{0}$$\left(\beta ©{V}_{1},{V}_{2},{V}_{3},{V}_{4}\beta ͺ,3\right)$.

Typical
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}>1$ $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}<$$\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• A value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that belongs to the $k$-th interval, of size $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}$, can be renamed to any unused value of the same interval.

• Two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that belong to two distinct intervals, of size $\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}$, can be swapped.

Arg. properties

Contractible wrt. $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 10 24 120 720 5040 40320 362880

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total1024120720504040320362880
 Parameter value

1624120720504040320362880
24------

Solution count for $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$: domains $0..n$

specialisation: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }/\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi Ά\pi Ώ\pi Ό\pi \pi \pi Έ}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\begin{array}{c}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }/\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}=\hfill \\ \mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }/\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}\hfill \end{array}$
Graph property(ies)
$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\beta €1$

Graph class
$\mathrm{\pi Ύ\pi ½\pi ΄}_\mathrm{\pi \pi \pi ²\pi ²}$

Graph model

Similar to the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint, but we replace the binary equality constraint of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint by the fact that two variables are respectively assigned to two values that belong to the same interval. We generate a clique with a belong to the same interval 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.17.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ graph property we show one of the largest strongly connected component of the final graph.

Automaton

FigureΒ 5.17.3 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint. To each item of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a signature variable ${\mathrm{\pi }}_{i}$ that is equal to 1. For each interval $\left[\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}Β·k,\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}Β·k+\mathrm{\pi \pi Έ\pi \pi ΄}_\mathrm{\pi Έ\pi ½\pi \pi ΄\pi \pi  \pi °\pi »}-1\right]$ of values the automaton counts the number of occurrences of its values and finally imposes that the values of an interval are taken at most once.