Link Search Menu Expand Document
Specifications PyCSP3 Tools Instances Competitions About

Meta-Constraint slide

A general mechanism, or meta-constraint, that is useful to post constraints on sequences of variables is slide [BHHKW08]. The scheme slide ensures that a given constraint is enforced all along a sequence of variables. To represent such sliding constraints in XCSP3, we simply build an element slide containing a constraint template (for example, one for extension or intension to indicate the abstract (parameterized) form of the constraint to be slided, preceded by an element list that indicates the sequence of variables on which the constraint must slide. Constraint templates are described in the full document about the specifications. The attribute circular of slideis optional (“false”, by default); when set to “true”, the constraint is slided circularly. The attribute offset of list is optional (value 1, by default); it permits, when sliding, to skip more than just one variable of the sequence, capturing slide_j in [BHHKW08].


<slide [ circular="boolean" ]>
    <list [ offset="integer" ]> (intVar wspace)2+ </list>
    <constraint .../> <!-- constraint template involving parameters -->

For the semantics, we consider that ctr(%0,...,%q-1) denotes the template of the constraint ctr of arity q, and that $slide^{circ}$ means the circular form of slide (i.e., with circular="true" in XCSP3).

  • slide($X$,ctr(%$0$,...,%$q-1$) with $X=\langle x_0,x_1,\ldots \rangle$, iff $\forall i : 0 \leq i \leq |X|-q$, ctr($x_i,x_{i+1},\ldots,x_{i+q-1}$)
  • slide($X$, $os$, ctr(%$0$,...,%$q-1$) with an offset $os$, iff $\forall i : 0 \leq i \leq (|X|-q)/os,$ ctr($x_{i \times os},x_{i \times os+1},\ldots,x_{i \times os+q-1}$)
  • slide($X^{circ}$,ctr(%$0$,...,%$q-1$), iff $\forall i : 0 \leq i \leq |X|-q+1$, ctr($x_i,x_{i + 1},\ldots,x_{(i + q - 1)\%|X|}$)

In the following example, c1 is the constraint x1 + x2 = x3 $\wedge$ x2 + x3 = x4, c2 is the circular sliding table constraint (y1,y2) $\in$ T $\wedge$ (y2,y3) $\in$ T $\wedge$ (y3,y4) $\in$ T $\wedge$ (y4,y1) $\in$ T with T={(a, a),(a,c),(b,b),(c,a),(c,b)} and c3 is the sliding ≠ constraint w1 $\neq$ z1 $\wedge$ w2 $\neq$ z2 $\wedge$ w3 $\neq$ z3, with offset 2.


<slide id="c1">
    <list>x1 x2 x3 x4</list>
<slide id="c2" circular="true">
    <list>y1 y2 y3 y4</list>
        <list>%0 %1</list>
<slide id="c3">
    <list offset="2">w1 z1 w2 z2 w3 z3</list>

Note that slide cannot be a descendant of (i.e., involved in) an element group, slide or seqbin.