## 5.16. alldifferent_except_0

 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 }_\mathtt{0}\left(\mathrm{\pi  \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 }_\mathtt{0}$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$.

Argument
 $\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)$
Restriction
$\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)$
Purpose

Enforce all variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ to take distinct values, except those variables that are assigned value 0.

Example
$\left(β©5,0,1,9,0,3βͺ\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$ constraint holds since all the values (that are different from 0) 5, 1, 9 and 3 are distinct.

All solutions

FigureΒ 5.16.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 }_\mathtt{0}$ constraint: ${V}_{1}\beta \left[0,4\right]$, ${V}_{2}\beta \left[1,2\right]$, ${V}_{3}\beta \left[1,2\right]$, ${V}_{4}\beta \left[0,1\right]$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$$\left(\beta ©{V}_{1},{V}_{2},{V}_{3},{V}_{4}\beta ͺ\right)$.

Typical
 $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>2$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$$\left(2,\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },0\right)$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$
Symmetries
• Items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are permutable.

• Two distinct values of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that are both different from 0 can be swapped; a value of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }$ that is different from 0 can be renamed to any unused value that is also different from 0.

Arg. properties

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

Usage

Quite often it appears that, for some modelling reason, you create a joker value. You do not want that normal constraints hold for variables that take this joker value. For this purpose we modify the binary arc constraint in order to discard the vertices for which the corresponding variables are assigned value 0. This will be effectively the case since all the corresponding arcs constraints will not hold.

Algorithm

An arc-consistency filtering algorithm for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$ constraint is described inΒ [Cymer12]. The algorithm is based on the following ideas:

• First, one can map solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$ constraint to var-perfect matchingsA var-perfect matching is a maximum matching covering all vertices representing variables. in a bipartite graph derived from the domain of the variables of the constraint in the following way: to each variable of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$ constraint corresponds a variable and a joker vertices, while to each potential value corresponds a value vertex; there is an edge between a variable vertex and a value vertex if and only if that value belongs to the domain of the corresponding variable; there is an edge between a variable vertex and its corresponding value vertex.

• Second, Dulmage-Mendelsohn decompositionΒ [DulmageMendelsohn58] is used to characterise all edges that do not belong to any var-perfect matching, and therefore prune the corresponding variables.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 7 34 209 1546 13327 130922 1441729

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

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)
 $\beta ’\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }=\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$$\beta €1$

Graph model

The graph model is the same as the one used for the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraint, except that we discard all variables that are assigned value 0.

PartsΒ (A) andΒ (B) of FigureΒ 5.16.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 components of the final graph. The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi ‘\pi \pi \pi \pi }_\mathtt{0}$ holds since all the strongly connected components have at most one vertex: a value different from 0 is used at most once.

Automaton

FigureΒ 5.16.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 }_\mathtt{0}$ constraint. To each variable ${\mathrm{\pi  \pi °\pi }}_{i}$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a 0-1 signature variable ${\mathrm{\pi }}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$ and ${\mathrm{\pi }}_{i}$: . The automaton counts the number of occurrences of each value different from 0 and finally imposes that each non-zero value is taken at most one time.