## 5.16. alldifferent_except_0

Origin
Constraint

$\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Synonyms

$\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$.

Argument
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restriction
$\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

Enforce all variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ to take distinct values, except those variables that are assigned value 0.

Example
$\left(〈5,0,1,9,0,3〉\right)$

The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$ constraint: ${V}_{1}\in \left[0,4\right]$, ${V}_{2}\in \left[1,2\right]$, ${V}_{3}\in \left[1,2\right]$, ${V}_{4}\in \left[0,1\right]$, $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$$\left(〈{V}_{1},{V}_{2},{V}_{3},{V}_{4}〉\right)$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$ $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}$$\left(2,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},0\right)$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• Two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that are both different from 0 can be swapped; a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that is different from 0 can be renamed to any unused value that is also different from 0.

Arg. properties

Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$ constraint is described in [Cymer12]. The algorithm is based on the following ideas:

• First, one can map solutions of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$: domains $0..n$

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\ne 0$ $•\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$$\le 1$

Graph model

The graph model is the same as the one used for the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$ graph property we show one of the largest strongly connected components of the final graph. The $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚎𝚡𝚌𝚎𝚙𝚝}_\mathtt{0}$ constraint. To each variable ${\mathrm{𝚅𝙰𝚁}}_{i}$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a 0-1 signature variable ${𝚂}_{i}$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_{i}$ and ${𝚂}_{i}$: ${\mathrm{𝚅𝙰𝚁}}_{i}\ne 0⇔{𝚂}_{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.