[BeldiceanuContejean94]

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

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

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

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.89.1 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.89.1. Graph of potential moves of the $6\times 6$ chessboard and corresponding balanced tours

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 of the corresponding $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint corresponds to the sequence A000142 of the On -Line Encyclopedia 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 of 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.

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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$.

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

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.

problems: pick-up delivery.

puzzles: Euler knight.

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

From the restrictions and from the arc constraint, we deduce that we have a bijection from the successor variables to the values of interval $[1,|\mathrm{𝙽𝙾𝙳𝙴𝚂}\left|\right]$. With no explicit restrictions it would have been impossible to derive this property.

In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices. This is why the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint considers objects that have two attributes:

• One fixed attribute $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ that is the identifier of the vertex,

• One variable attribute $\mathrm{𝚜𝚞𝚌𝚌}$ that is the successor of the vertex.

The graph property $\mathrm{𝐍𝐓𝐑𝐄𝐄}$ $=$ 0 is used in order to avoid having vertices that both do not belong to a circuit and have at least one successor located on a circuit. This concretely means that all vertices of the final graph should belong to a circuit.

Parts (A) and (B) of Figure 5.89.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐂𝐂}$ graph property, we show the two connected components of the final graph. The constraint holds since all the vertices belong to a circuit (i.e., $\mathrm{𝐍𝐓𝐑𝐄𝐄}$ $=$ 0) and since $\mathrm{𝙽𝙲𝚈𝙲𝙻𝙴}$ $=$ $\mathrm{𝐍𝐂𝐂}$ $=$ 2.

Figure 5.89.2. Initial and final graph of the $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ constraint

(a)	(b)