does hinder propagation, but only when dom(N) contains just **card**↓(X) and **card**↑(X)
and there is a gap in the domain in-between (see Theorem 1 in [13] and the discussion that follows). When enforcing BC, any such gap in the domain for N is ignored.

## 4 Atmostnvalue Constraint

We now give a decomposition for the ATMOSTNVALUE constraint which does not hinder bound consistency propagation. To decompose the ATMOSTNVALUE constraint, we introduce 0/1 variables, Ailu to represent whether Xi uses a value in the interval [**l, u**], and "pyramid" variables, Mlu with domains [0, min (u − l + 1, n)] which count the number of values taken inside the interval [**l, u**]. To constrain these introduced variables, we post the following constraints:

$$A_{ilu}=1\iff X_{i}\in[l,u]\quad\forall\;1\leq i\leq n,1\leq l\leq u\leq d\tag{4}$$ $$A_{ilu}\leq M_{lu}\qquad\qquad\forall\;1\leq i\leq n,1\leq l\leq u\leq d$$ (5) $$M_{1u}=M_{1k}+M_{(k+1)u}\quad\quad\forall\;1\leq k<u\leq d$$ (6) $$M_{1d}\leq N\tag{7}$$

Running Example. *Consider the decomposition of an* ATMOSTNVALUE *constraint* over the following variables and values:

![0_image_0.png](0_image_0.png)

Observe that we consider that value 5 for N *has already been pruned by* ATLEASTNVALUE*, as will be shown in next sections. Bound consistency reasoning* on the decomposition will make the following inferences. As X2 = 2*, from* (4) we get A222 = 1*. Hence by* (5), M22 = 1*. Similarly, as* X4 = 4*, we get* A444 = 1 and M44 = 1*. Now* N ∈ {1, 2}*. By* (7) and (6), M15 ≤ N, M15 = M14 + M55, M14 = M13 + M44, M13 = M12 + M33, M12 = M11 + M22*. Since* M22 = M44 = 1, we deduce that N > 1 *and hence* N = 2*. This gives* M11 = M33 = M55 = 0*. By* (5),
A111 = A133 = A155 = A533 = 0*. Finally, from* (4)*, we get* X1 = 2 and X5 = 3*. This* gives us bound consistent domains for the ATMOSTNVALUE *constraint.*
We now prove that this decomposition does not hinder propagation in general.

Theorem 3 *BC on constraints (4) to (7) is equivalent to BC on* ATMOSTNVALUE
([X1, . . . , Xn], N), and takes O(nd3) time to enforce down the branch of the search tree.

Proof: First note that changing the domains of the X variables cannot affect the upper bound of N by the ATMOSTNVALUE constraint and, conversely, changing the lower bound of N cannot affect the domains of the X variables.