5.37. atleast_nvalue
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
The number of distinct values taken by the variables of the collection is greater than or equal to .
- Example
-
The first constraint holds since the collection involves at least 2 distinct values (i.e.,Β in fact 4 distinct values).
- Typical
- Symmetries
can be decreased to any value .
Items of are permutable.
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Arg. properties
Extensible wrt. .
- Remark
The constraint was first introduced by J.-C. Régin under the name in [Regin95]. Later on the constraint was introduced together with the constraint by C. Bessière et al. in an article [BessiereHebrardHnichKiziltanWalsh05] providing filtering algorithms for the constraint.
- Algorithm
[BessiereHebrardHnichKiziltanWalsh05] provides a sketch of a filtering algorithm enforcing arc-consistency for the constraint. This algorithm is based on the maximal matching in a bipartite graph.
- Counting
-
Length () 2 3 4 5 6 7 8 Solutions 24 212 2470 35682 614600 12286024 279472266 Number of solutions for : domains
Length () 2 3 4 5 6 7 8 Total 24 212 2470 35682 614600 12286024 279472266 Parameter value 0 9 64 625 7776 117649 2097152 43046721 1 9 64 625 7776 117649 2097152 43046721 2 6 60 620 7770 117642 2097144 43046712 3 - 24 480 7320 116340 2093616 43037568 4 - - 120 4320 97440 1992480 42550704 5 - - - 720 42840 1404480 37406880 6 - - - - 5040 463680 21530880 7 - - - - - 40320 5443200 8 - - - - - - 362880 Solution count for : domains
- See also
-
implied by: , , , , , Β ( replaced by ), , , , , , .
- Keywords
constraint type: counting constraint, value partitioning constraint.
filtering: bipartite matching, arc-consistency.
final graph structure: strongly connected component, equivalence.
modelling: number of distinct equivalence classes, number of distinct values.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.37.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a specific value that is assigned to some variables of the collection. The 4 following values 1, 3, 6 and 7 are used by the variables of the collection.
Figure 5.37.1. Initial and final graph of the constraint
(a) 
(b)