Global Constraint Catalog: Calldifferent

5.15. alldifferent_cst

DESCRIPTION

LINKS

GRAPH

Origin

CHIP

Constraint

$𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Synonyms

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

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛, 𝚌𝚜𝚝 - 𝚒𝚗𝚝)

Restriction

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, [𝚟𝚊𝚛, 𝚌𝚜𝚝])

Purpose

For all pairs of items $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i], 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [j])$ $(i \neq j)$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ enforce $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚟𝚊𝚛 + 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i] . 𝚌𝚜𝚝 \neq 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [j] . 𝚟𝚊𝚛 + 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [j] . 𝚌𝚜𝚝$ .

Example

(\begin{matrix} 〈\begin{matrix} 𝚟𝚊𝚛 - 5 & 𝚌𝚜𝚝 - 0, \\ 𝚟𝚊𝚛 - 1 & 𝚌𝚜𝚝 - 1, \\ 𝚟𝚊𝚛 - 9 & 𝚌𝚜𝚝 - 0, \\ 𝚟𝚊𝚛 - 3 & 𝚌𝚜𝚝 - 4 \end{matrix}〉 \end{matrix})

The $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint holds since all the expressions $5 + 0 = 5$ , $1 + 1 = 2$ , $9 + 0 = 9$ and $3 + 4 = 7$ correspond to distinct values.

All solutions

Figure 5.15.1 gives all solutions to the following non ground instance of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint: $V_{1} \in [0, 2]$ , $V_{2} \in [4, 5]$ , $V_{3} \in [4, 4]$ , $V_{4} \in [0, 1]$ , $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ $(〈 〈 V_{1}, 0 〉, 〈 V_{2}, 1 〉, 〈 V_{3}, 2 〉, 〈 V_{3}, 3 〉 〉)$ .

Figure 5.15.1. All solutions corresponding to the non ground example of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint of the All solutions slot

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 2

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

2 *

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) < 3 * | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚌𝚜𝚝) > 1

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
Attributes of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable w.r.t. permutation $(𝚟𝚊𝚛, 𝚌𝚜𝚝)$ (permutation not necessarily applied to all items).
One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
One and the same constant can be added to the $𝚌𝚜𝚝$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Arg. properties

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

Usage

The $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint was originally introduced in CHIP in order to express the $n$ -queen problem with 3 global constraints (see the Usage slot of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint).

Algorithm

See the filtering algorithms of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint.

Systems

linear in Gecode.

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

Keywords

characteristic of a constraint: all different, disequality, sort based reformulation.

constraint type: value constraint.

filtering: bipartite matching, bipartite matching in convex bipartite graphs, convex bipartite graph, arc-consistency.

final graph structure: one_succ.

modelling exercises: n-Amazons.

puzzles: n-Amazons, n-queens.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

\begin{matrix} 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 + 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚌𝚜𝚝 = \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 + 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚌𝚜𝚝 \end{matrix}

Graph property(ies)

𝐌𝐀𝐗_𝐍𝐒𝐂𝐂

\leq 1

Graph class

𝙾𝙽𝙴_𝚂𝚄𝙲𝙲

Graph model

We generate a clique with an equality 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 one.

Parts (A) and (B) of Figure 5.15.2 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. The $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ holds since all the strongly connected components have at most one vertex: a value is used at most once.

Figure 5.15.2. Initial and final graph of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.15. alldifferent_cst

Figure 5.15.1. All solutions corresponding to the non ground example of the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝 constraint of the All solutions slot

Figure 5.15.2. Initial and final graph of the 𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝 constraint

Figure 5.15.1. All solutions corresponding to the non ground example of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint of the All solutions slot

Figure 5.15.2. Initial and final graph of the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝_𝚌𝚜𝚝$ constraint