[BeldiceanuContejean94]

$\mathrm{𝚌𝚢𝚌𝚕𝚎}(\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴},\mathrm{𝙽𝙾𝙳𝙴𝚂})$

• In the first example we have the following 2 ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}=2$) cycles: $1\mapsto 2\mapsto 1$ and $3\mapsto 5\mapsto 4\mapsto 3$. Consequently, the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint holds.

• In the second example we have 1 ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}=1$) cycle: $1\mapsto 2\mapsto 5\mapsto 4\mapsto 3\mapsto 1$.

• In the third example we have the following 5 ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}=5$) cycles: $1\mapsto 1$, $2\mapsto 2$, $3\mapsto 3$, $4\mapsto 4$ and $5\mapsto 5$.

Figure 5.103.1 gives all solutions to the following non ground instance of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint: $N\in [1,2]$, $V_1\in [2,4]$, $V_2\in [2,3]$, $V_3\in [1,6]$, $V_4\in [2,5]$, $V_5\in [2,3]$, $V_6\in [1,6]$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$$(N,\langle 1V_1,2V_2,3V_3,4V_4,5V_5,6V_6\rangle )$.

Figure 5.103.1. All solutions corresponding to the non ground example of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint of the All solutions slot

• Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

• Attributes of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable w.r.t. permutation $(\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌})$ (permutation applied to all items).

Functional dependency: $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ determined by $\mathrm{𝙽𝙾𝙳𝙴𝚂}$.

The PhD thesis of Éric Bourreau [Bourreau99] mentions the following applications of extensions of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint:

• The balanced Euler knight problem where one tries to cover a rectangular chessboard of size $N·M$ by $C$ knights that all have to visit between $2·\lfloor \lfloor (N·M)/C\rfloor /2\rfloor$ and $2·\lceil \lceil (N·M)/C\rceil /2\rceil$ distinct locations. For some values of $N$, $M$ and $C$ there does not exist any solution to the previous problem. This is for instance the case when $N=M=C=6$. Figure 5.103.2 depicts the graph associated with the $6\times 6$ chessboard as well as examples of balanced solutions with respectively 1, 2, 3, 4 and 5 knights.

• Some pick-up delivery problems where a fleet of vehicles has to transport a set of orders. Each order is characterised by its initial location, its final destination and its weight. In addition one also has to take into account the capacity of the different vehicles.

Figure 5.103.2. Graph of potential moves of a $6\times 6$ chessboard, corresponding balanced knight's tours with 1 up to 5 knights, and collection of nodes passed to the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponding to the solution with 5 knights; note that their is no balanced knight's tour on a $6\times 6$ chessboard where each knight exactly performs 6 moves.

In the original $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint of CHIP the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.

In an early version of the CHIP there was a constraint named $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ that, from a declarative point of view, was equivalent to $\mathrm{𝚌𝚢𝚌𝚕𝚎}(1,\mathrm{𝙽𝙾𝙳𝙴𝚂})$. In ALICE [Lauriere78] the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint was also present.

Given a complete digraph of $n$ vertices as well as an unrestricted number of circuits $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$, the total number of solutions to the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponds to the sequence A000142 of the On-Line Encyclopaedia of Integer Sequences [Sloane10]. Given a complete digraph of $n$ vertices as well as a fixed number of circuits $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ between 1 and $n$, the total number of solutions to the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponds to the so called Stirling number of first kind.

Since all $\mathrm{𝚜𝚞𝚌𝚌}$ variables have to take distinct values one can reuse the algorithms associated with the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint. A second necessary condition is to have no more than $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components. Pruning for enforcing this condition, as soon as we have $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components, can be done by forcing all strong bridges to belong to the final solution, since otherwise we would have more than $\overline{\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}}$ strongly connected components. Since all the vertices of a circuit belong to the same strongly connected component an arc going from one strongly connected component to another strongly connected component has to be removed.

Let $n$ and $s_1,s_2,\cdots ,s_n$ respectively denotes the number of vertices (i.e., $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$) and the successor variables associated with vertices $1,2,\cdots ,n$. The $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint can be reformulated as a conjunction of one $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint, $n·(n-1)$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints, $n$ $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraints, and one $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint.

• First, we state an

  $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle s_1,s_2,\cdots ,s_n\rangle \right)$ constraint for enforcing distinct values to be assigned to the successor variables.

• Second, the key idea is to extract for each vertex $i$ (with $i\in [1,n]$) all the vertices that belong to the same cycle. This is done by stating a conjunction of $n-1$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints of the form:

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(i,\langle s_1,s_2,\cdots ,s_n\rangle ,s_{i,1})$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(s_{i,1},\langle s_1,s_2,\cdots ,s_n\rangle ,s_{i,2})$,

   $\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(s_{i,n-2},\langle s_1,s_2,\cdots ,s_n\rangle ,s_{i,n-1})$.

  Then, using a $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$$(m_i,$ $\langle i,s_{i,1},s_{i,2},\cdots ,s_{i,n-1}\rangle )$ constraint, we get a unique representative for the cycle containing vertex $i$.

• Third, using a $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$(\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴},$ $\langle m_1,m_2,\cdots ,m_n\rangle )$ constraint, we get the number of distinct cycles.

Number of solutions for $\mathrm{𝚌𝚢𝚌𝚕𝚎}$: domains $0..n$

Solution count for $\mathrm{𝚌𝚢𝚌𝚕𝚎}$: domains $0..n$

common keyword: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (permutation),

$\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\_\mathrm{𝚌𝚕𝚞𝚜𝚝𝚎𝚛}$ (graph constraint, one_succ),

$\mathrm{𝚌𝚢𝚌𝚕𝚎}\_\mathrm{𝚌𝚊𝚛𝚍}\_\mathrm{𝚘𝚗}\_\mathrm{𝚙𝚊𝚝𝚑}$ (permutation,graph partitioning constraint),

$\mathrm{𝚌𝚢𝚌𝚕𝚎}\_\mathrm{𝚘𝚛}\_\mathrm{𝚊𝚌𝚌𝚎𝚜𝚜𝚒𝚋𝚒𝚕𝚒𝚝𝚢}$ (graph constraint),

$\mathrm{𝚌𝚢𝚌𝚕𝚎}\_\mathrm{𝚛𝚎𝚜𝚘𝚞𝚛𝚌𝚎}$ (graph partitioning constraint),

$\mathrm{𝚍𝚎𝚛𝚊𝚗𝚐𝚎𝚖𝚎𝚗𝚝}$ (permutation),

$\mathrm{𝚐𝚛𝚊𝚙𝚑}\_\mathrm{𝚌𝚛𝚘𝚜𝚜𝚒𝚗𝚐}$ (graph constraint,graph partitioning constraint),

$\mathrm{𝚒𝚗𝚟𝚎𝚛𝚜𝚎}$ (permutation),

$\mathrm{𝚖𝚊𝚙}$ (graph partitioning constraint),

$\mathrm{𝚜𝚢𝚖𝚖𝚎𝚝𝚛𝚒𝚌}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (permutation),

$\mathrm{𝚝𝚘𝚞𝚛}$ (graph constraint),

$\mathrm{𝚝𝚛𝚎𝚎}$ (graph partitioning constraint).

implies: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$.

implies (items to collection): $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}\_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$.

related: $\mathrm{𝚋𝚊𝚕𝚊𝚗𝚌𝚎}\_\mathrm{𝚌𝚢𝚌𝚕𝚎}$ (counting number of cycles versus controlling how balanced the cycles are).

specialisation: $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ ($\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ set to 1).

used in reformulation: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$, $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$, $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

characteristic of a constraint: core.

combinatorial object: permutation.

constraint arguments: business rules.

constraint type: graph constraint, graph partitioning constraint.

filtering: strong bridge, DFS-bottleneck.

final graph structure: circuit, connected component, strongly connected component, one_succ.

modelling: cycle, functional dependency.

problems: pick-up delivery.

puzzles: Euler knight.