5.5. alldifferent

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Lauriere78]

Constraint

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

πšŠπš•πš•πšπš’πšπš, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš, πšπš’πšœπšπš’πš—πšŒπš, πš‹πš˜πšžπš—πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš‹πš˜πšžπš—πš_πšŠπš•πš•πšπš’πšπš, πš‹πš˜πšžπš—πš_πšπš’πšœπšπš’πš—πšŒπš, πš›πšŽπš•.

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restriction
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Enforce all variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to take distinct values.

Example
(5,1,9,3)

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint holds since all the values 5, 1, 9 and 3 are distinct.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • Two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be swapped; a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› can be renamed to any unused value.

Usage

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint occurs in most practical problems directly or indirectly. A classical example is the n-queen chess puzzle problem: Place n queens on a n by n chessboard in such a way that no queen attacks another. Two queens attack each other if they are located on the same column, on the same row or on the same diagonal. This can be modelled as the conjunction of three πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints. We associate to the i th column of the chessboard a domain variable X i that gives the row number where the corresponding queen is located. The three πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints are:

  • πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(X 1 ,X 2 +1,...,X n +n-1) for the upper-left to lower-right diagonals,

  • πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(X 1 ,X 2 ,...,X n ) for the rows,

  • πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(X 1 +n-1,X 2 +n-2,...,X n ) for the lower right to upper-left diagonals.

They are respectively depicted by partsΒ (A), (C) and (D) of FigureΒ 5.5.1.

Figure 5.5.1. Upper-left to lower-right diagonals (A-B), rows (C) and lower-right to upper-left diagonals (D-E)
ctrs/alldifferent2

A second example taken fromΒ [AsratianDenleyHaggkvist98] when the bipartite graph associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is convex is a ski assignment problem: β€œa set of skiers have each specified the smallest and largest skis they will accept from a given set of skis”. The task is to find a ski for each skier.

Examples such as Costas arrays or Golomb rulers involve one or several πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints on differences of variables.

Quite often, the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is also used in conjunction with several πšŽπš•πšŽπš–πšŽπš—πš constraints, specially in the context of assignment problemsΒ [pages 372–374][Hooker07book].

Other examples involving several πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints sharing some variables can be found in the Usage slot of the πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint.

Remark

Even if the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint had not this form, it was specified in ALICEΒ [Lauriere76], [Lauriere78] by asking for an injective correspondence between variables and values: xβ‰ yβ‡’f(x)β‰ f(y). From an algorithmic point of view, the algorithm for computing the cardinality of the maximum matching of a bipartite graph was not used for checking the feasibility of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, even if the algorithm was already known in 1976. This stands from the fact that the goal of ALICE was to show that a general system could be as efficient as dedicated algorithms. For this reason the concluding part ofΒ [Lauriere76] explicitly mentions the fact that specialized algorithms should be discarded. On the one hand, many people, specially from the OR community, have complained about such radical statementΒ [Roy06]. On the other hand, the motivation of such statement stands from the fact that a truly intelligent system should not rely on black box algorithms, but should rather be able to reconstruct them from some kind of first principle. How to achieve this is still an open question.

Some solvers use in a pre -processing phase before stating all constraints, an algorithm for automatically extracting large cliquesΒ [BronKerbosch73] from a set of binary disequalities in order to replace them by πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints.

W.-J.Β vanΒ Hoeve provides a survey about the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint inΒ [Hoeve01].

For possible relaxation of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints see the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0, the πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš (i.e.,Β πšœπš˜πš–πšŽ_πšπš’πšπšπšŽπš›πšŽπš—πš), the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš›, the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš› and the πš πšŽπš’πšπš‘πšπšŽπš_πš™πšŠπš›πšπš’πšŠπš•_πšŠπš•πš•πšπš’πšπš constraints.

Within the context of linear programming, relaxations of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint are described inΒ [WilliamsYan01] and inΒ [Hooker07book].

Within the context of constraint-centered search heuristics, G.Β Pesant and A.Β ZanariniΒ [ZanariniPesant07b] have proposed several estimators for evaluating the number of solutions of an πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint (since counting the total number of maximum matchings of the corresponding variable -value graph is #P -completeΒ [Valiant79]). Faster, but less accurate estimators, based on upper bounds of the number of solutions were proposed three years later by the same authorsΒ [ZanariniPesant10].

Given n variables taking their values within the interval [1,n], the total number of solutions of the corresponding πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint corresponds to the sequence A000142 of the On -Line Encyclopedia of Integer SequencesΒ [Sloane10].

Algorithm

The first complete filtering algorithm was independently found by M.-C.Β CostaΒ [Costa94] and J.-C.Β RΓ©ginΒ [Regin94]. This algorithm is based on a corollary of C.Β Berge that characterises the edges of a graph that belong to a maximum matching but not to allΒ [Berge70].A similar result is in fact given inΒ [Petersen1891]. A short time after, assuming that all variables have no holes in their domain, M.Β Leconte came up with a filtering algorithmΒ [Leconte96] based on edge finding. A first bound-consistency algorithm was proposed by Bleuzen-Guernalec et al.Β [GuernalecColmerauer97]. Later on, two different approaches were used to design bound-consistency algorithms. Both approaches model the constraint as a bipartite graph. The first identifies Hall intervals in this graphΒ [Puget98], [LopezOrtizQuimperTrompBeek03] and the second applies the same algorithm that is used to compute arc-consistency, but achieves a speedup by exploiting the simpler structureΒ [Glover67] of the graphΒ [MehlhornThiel00]. Ian P. Gent et al. discuss inΒ [GentMiguelNightingale08] implementations issues behind the complete filtering algorithm and in particular the computation of the strongly connected components of the residual graph (i.e.,Β a graph constructed from a maximum variable -value matching and from the possible values of the variables of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint), which appears to be the main bottleneck in practice.

From a worst case complexity point of view, assuming that n is the number of variables and m the sum of the domains sizes, we have the following complexity results:

  • Complete filtering is achieved in O(mn) by RΓ©gin's algorithmΒ [Regin94].

  • Range consistency is done in O(n 2 ) by Leconte's algorithm [Leconte96].

  • Bound-consistency is performed in O(nlogn) inΒ [Puget98], [MehlhornThiel00], [LopezOrtizQuimperTrompBeek03]. If sort can be achieved in linear time, typically when the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint encodes a permutation,In this context the total number of values that can be assigned to the variables of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is equal to the number of variables. Under this assumption sorting the variables on their minimum or maximum values can be achieved in linear time. the worst case complexity of the algorithms described inΒ [MehlhornThiel00], [LopezOrtizQuimperTrompBeek03] goes down to O(n).

Within the context of explanationsΒ [JussienBarichard00], the explanation of the filtering algorithm that achieves arc-consistency for the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is described inΒ [Rochart05]. Given the residual graph (i.e.,Β a graph constructed from a maximum variable -value matching and from the possible values of the variables of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint), the removal of an arc starting from a vertex belonging to a strongly connected component π’ž 1 to a distinct strongly connected component π’ž 2 is explained by all missing arcs starting from a descendant component of π’ž 2 and ending in an ancestor component of π’ž 1 (i.e.,Β since the addition of any of these missing arcs would merge the strongly connected components π’ž 1 and π’ž 2 ). Let us illustrate this on a concrete example. For this purpose assume we have the following variables and the values that can potentially be assigned to each of them, A∈{1,2}, B∈{1,2}, C∈{2,3,4,6}, D∈{3,4}, E∈{5,6}, F∈{5,6}, G∈{6,7,8}, H∈{6,7,8}. FigureΒ 5.5.2 represents the residual graph associated with the maximum matching corresponding to the assignment A=1, B=2, C=3, D=4, E=5, F=6, G=7, H=8. It has four strongly connected components containing respectively vertices {A,B,1,2}, {C,D,3,4}, {E,F,5,6} and {G,H,7,8}. Arcs that are between strongly connected components correspond to values that can be removed:

  • The removal of value 2 from variable C is explained by the absence of the arcs corresponding to the assignments A=3, A=4, B=3 and B=4 (since adding any of these missing arcs would merge the blue and the pink strongly connected components containing the vertices corresponding to value 2 and variable C).

  • The removal of value 6 from variable C is explained by the absence of the arcs corresponding to the assignments E=3, E=4, F=3 and F=4. Again adding the corresponding arcs would merge the two strongly connected components containing the vertices corresponding to value 6 and variable C.

  • The removal of value 6 from variable G is explained by the absence of the arcs corresponding to the assignments E=7, E=8, F=7 and F=8.

  • The removal of value 6 from variable H is explained by the absence of the arcs corresponding to the assignments E=7, E=8, F=7 and F=8.

Figure 5.5.2. Strongly connected components of the residual graph illustrating the explanation of the removal of a value for the constraint πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(〈A,B,C,D,E,F,G,HβŒͺ), A∈{1,2}, B∈{1,2}, C∈{2,3,4,6}, D∈{3,4}, E∈{5,6}, F∈{5,6}, G∈{6,7,8}, H∈{6,7,8}: the explanation why value 2 is removed from variable C corresponds to all missing arcs whose addition would merge the blue and the pink strongly connected components (i.e.,Β the missing arcs corresponding to the assignments A=3, A=4, B=3 and B=4 that are depicted by thick pink lines)
ctrs/alldifferent3

After applying bound-consistency the following property holds for all variables of an πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint. Given a Hall interval [l,u], any variable V whose range [V Μ²,V Β―] intersects [l,u] without being included in [l,u] has its minimum value V Μ² (respectively maximum value V Β―) that is located before (respectively after) the Hall interval (i.e.,Β V Μ²<l≀u<V Β―).

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is entailed if and only if there is no value v that can be assigned two distinct variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection (i.e.,Β the intersection of the two sets of potential values of any pair of variables is empty).

Reformulation

The πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint can be reformulated into a set of disequalities constraints. This model neither preserves bound-consistency nor arc-consistency:

  • On the one hand a model, involving linear constraints, preserving bound-consistency was introduced inΒ [BessiereKatsirelosNarodytskaQuimperWalsh09IJCAI]. For each potential interval [l,u] of consecutive values this model uses |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| 0-1 variables B 1,l,u ,B 2,l,u ,...,B |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|,l,u for modelling the fact that each variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ is assigned a value within interval [l,u] (i.e.,Β βˆ€i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]:B i,l,u β‡”πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›βˆˆ[l,u]),How to encode the reified constraint B i,l,u β‡”πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš›βˆˆ[l,u] with linear constraints is described in the Reformulation slot of the πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•_πš›πšŽπš’πšπš’πšŽπš constraint. and an inequality constraint for enforcing the condition that the sum of the corresponding 0-1 variables is less than or equal to the size u-l+1 of the corresponding interval (i.e.Β B 1,l,u +B 2,l,u +...+B |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|,l,u ≀u-l+1).

  • On the other hand, it was shown inΒ [BessiereKatsirelosNarodytskaWalsh09] that there is no polynomial sized decomposition that preserves arc-consistency.

Systems

allDifferent in Choco, distinct in Gecode, rel in Gecode, alldifferent in JaCoP, alldiff in JaCoP, alldistinct in JaCoP, all_different in SICStus, all_distinct in SICStus.

Used in

πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš•πšžπšŽπšœ, πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš›, πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽ, πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_πšŒπš˜πš—πšŸπšŽπš‘, πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšœπš’πš£πšŽ_πš–πšŠπš‘_πšœπšπšŠπš›πšπš’πš—πš_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšœπš˜πš›πš_πš™πšŽπš›πš–πšžπšπšŠπšπš’πš˜πš—.

See also

common keyword: πšŒπš’πš›πšŒπšžπš’πš, πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš›, πšŒπš’πšŒπš•πšŽ, πšπšŽπš›πšŠπš—πšπšŽπš–πšŽπš—πšΒ (permutation), πšπš˜πš•πš˜πš–πš‹Β (all different), πšœπš’πš£πšŽ_πš–πšŠπš‘_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πšœπš’πš£πšŽ_πš–πšŠπš‘_πšœπšπšŠπš›πšπš’πš—πš_𝚜𝚎𝚚_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (all different,disequality), πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation).

cost variant: πš–πš’πš—πš’πš–πšžπš–_πš πšŽπš’πšπš‘πš_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš πšŽπš’πšπš‘πšπšŽπš_πš™πšŠπš›πšπš’πšŠπš•_πšŠπš•πš•πšπš’πšπš.

generalisation: πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πš•πš’πš—πšŽ πšœπšŽπšπš–πšŽπš—πš, all of the same size), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš‹πšŽπšπš πšŽπšŽπš—_𝚜𝚎𝚝𝚜 (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by 𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_𝚌𝚜𝚝 (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ+πšŒπš˜πš—πšœπšπšŠπš—πš), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš•Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš˜πšπšžπš•πš˜Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš), πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—), πšπš’πšπšπš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by orthotope), πšπš’πšœπš“πšžπš—πšŒπšπš’πšŸπšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšπšŠπšœπš”), πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’Β (control the number of occurrence of each value with a counter variable), πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™Β (control the number of occurrence of each value with an interval), πš•πšŽπš‘_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŽπšŒπšπš˜πš›), πš—πšŸπšŠπš•πšžπšŽΒ (count number of distinct values).

implied by: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš•πšžπšŽπšœ, πšŒπš’πš›πšŒπšžπš’πš, πšŒπš’πšŒπš•πšŽ, πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš, πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

implies: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0, πš—πš˜πš_πšŠπš•πš•_πšŽπššπšžπšŠπš•.

part of system of constraints: πš—πšŽπšš.

shift of concept: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš˜πš—_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—, πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšœπšŠπš–πšŽ_πšŸπšŠπš•πšžπšŽ.

soft variant: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŽπš‘πšŒπšŽπš™πš_0Β (value 0 can be used several times), πš˜πš™πšŽπš—_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (open constraint), 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš›Β (decomposition-based violation measure), 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš›Β (variable-based violation measure).

system of constraints: πš”_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

used in reformulation: πš’πš—_πš’πš—πšπšŽπš›πšŸπšŠπš•_πš›πšŽπš’πšπš’πšŽπšΒ (bound-consistency preserving reformulation).

uses in its reformulation: πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Keywords

characteristic of a constraint: core, all different, disequality, automaton, automaton with array of counters.

combinatorial object: permutation.

constraint type: system of constraints, value constraint.

filtering: bipartite matching, bipartite matching in convex bipartite graphs, convex bipartite graph, flow, Hall interval, arc-consistency, bound-consistency, SAT, DFS-bottleneck, entailment.

final graph structure: one_succ.

modelling exercises: n-Amazon, zebra puzzle.

problems: maximum clique, graph colouring.

puzzles: n-Amazon, n-queen, Costas arrays, Euler knight, Golomb ruler, magic hexagon, magic square, zebra puzzle, Sudoku.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀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.5.3 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 component 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.5.3. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/alldifferentActrs/alldifferentB
(a) (b)
Automaton

FigureΒ 5.5.4 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 1. The automaton counts the number of occurrences of each value and finally imposes that each value is taken at most one time.

Figure 5.5.4. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint
ctrs/alldifferent1