Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About

Cheat Sheet

Many succinct illustrative examples about how to specify data, declare variables, post constraints and specify an objective.

1) Specifying Data

python Queens.py -data=8                       # a single elementary value (integer)

python BIBD.py -data=[9,0,0,3,9]               # a list of elementary values
python BIBD.py -data=[v=9,b=0,r=0,k=3,l=9]     # a list of named elementary values

python Sudoku.py -data=puzzle.txt -parser=ParserSudoku.py          # a text file (needs a parser)
python Sudoku.py -data=puzzle.json                                 # a JSON file
python Sudoku.py -data=https://raw.mysite.com/puzzle.json          # a JSON file from an URL

python Test.py -data=[file1.json,file2.json]                       # several JSON files
python Test.py -data=[file1.json,file2.json,c=5]                   #   with an additional field

python Test2.py -data=[file1.txt,file2.txt] -parser=Parser2.py     # several text files
python Test2.py -data=[file1.txt,file2.txt,10] -parser=Parser2.py  #   with an additional line

2) Declaring Variables

# single variables
v = Var(dom=range(15))        # a variable with domain {0, 1,..., 14}
b = Var(0, 1)                 # a 0/1 variable (can be seen as a Boolean variable)
v = Var(dom=(0, 2, 4, 6, 8))  # a variable with domain {0, 2, 4, 6, 8}
v = Var(dom={"a", "b", "c"})  # a Variable with symbolic domain {a, b, c}

# arrays of variables
x = VarArray(size=10, dom={0, 1})          # a 1-dimensional array of 0/1 variables  
m = VarArray(size=[5, 5], dom=range(10))   # a 2-dimensional array of variables with domain {0, 1,... ,9}
c = VarArray(size=[4, 3, 4], dom={1, 5, 10, 20})  # a 3-dimensional array of variables

# arrays of variables with different domains
m = VarArray(size=[5, 5], dom=lambda i,j: range(5) if j == 0 else range(10))

print(m[:,j])        # print the jth column of m (indexing as in NumPy) 
print(m[0:3,0:3])    # print a block of m (indexing as in NumPy) 

3) Posting constraints

satisfy(
  AllDifferent(x)                      # a single constraint              
)

satisfy(
  x[i] < 10 for i in range(n)          # a group (generator) of constraints 
)

satisfy(
  AllDifferent(x),                     # a first constraint

  [x[i] < 10 for i in range(n)]        # followed by a list of constraints
)

4) Building Constraints (to be posted)

In the following:

  • v, w, b refer to single variables
  • x, y, z refer to 1-dimensional arrays of variables
  • m, m1, m2 refer to 2-dimensional (matrix) of variables

AllDifferent

Some variables (or expressions) must take different values.

AllDifferent(x[0], x[3], x[8])  # the three variable must take different values 
AllDifferent(x)                 # all variables in x must take different values
AllDifferent(x, excepting=0)    # all variables in x, different from 0, must take different values

AllDifferent(abs(x[1]-x[0]), abs(x[2]-x[1]), abs(x[3]-x[2]))  # with a sequence of expressions
AllDifferent(abs(x[i+1]-x[i]) for i in range(3))              # with a generator of expressions

AllDifferent(m, matrix=True)               # all rows and columns must have different values
AllDifferent(m, matrix=True, excepting=0)  #   (while ignoring the value 0)  

AllEqual

Some variables (or expressions) must take equal values.

AllEqual(x[0], x[3], x[8])                                # the three variables must take equal values 
AllEqual(abs(x[1]-x[0]), abs(x[2]-x[1]), abs(x[3]-x[2]))  # the three expressions must take equal values

BinPacking

A list of items, whose sizes are given, must be put in different bins in such a way that a condition in terms of capacity is respected for each bin.

x = VarArray(size=6, dom={0, 1, 2})     # 6 items to possibly be put in bins 0, 1 and 2

BinPacking(x, sizes=[8,7,3,9,5,7]) <= 12               # the capacity of each bin is 12
BinPacking(x, sizes=[8,7,3,9,5,7], limits=[9,12,11])   # capacity of bins 0, 1 and 2 are 9, 12 and 11 

BinPacking(x, sizes=[8,7,3,9,5,7], loads=[y[0],y[2],y[4]])  # load of bins given by variables of y      

Cardinality

The number of occurrences of certain values, taken by the variables of a list, must be restrained by an integer, a variable or an interval.

Cardinality(x, occurrences={0:3, 1:2, 2:3})             # 0 must occur 3 times, 1 two times, 2 ...
Cardinality(x, occurrences={0:3, 1:range(2,5), 2:3})    # 1 must occur between 2 and 4 times

Cardinality(x, occurrences={i:y[i] for i in range(3)})  # i must occur y[i] times

Channel

A correspondence between indexes and values of a single list has to be respected. This may also be imposed for two lists, or between a list of variables 0/1 and an integer variable.

x = VarArray(size=5, dom=range(5))
y = VarArray(size=5, dom=range(5))

Channel(x)    # imposes x[i] = j  <=> x[j] = i
Channel(x,y)  # imposes x[i] = j <=> y[j] = i

z = VarArray(size=6, dom={0,1})
v = Var(range(6))

Channel(z,v)   # imposes z[i] = 1 <=> v=i  

Circuit

The values taken by some variables must form a circuit, with the assumption that each pair (i, x[i]) represents an arc.

x = VarArray(size=6, dom=range(6))

Circuit(x)          # circuit of any size (self-loop are ignored)

Circuit(x, size=3)  # circuit of size 3 
Circuit(x, size=v)  # circuit of size given by v

Count

The number of variables from a specified list that take their values from a specified set (often, a single value) must respect a numerical condition.

Count(x, value=1) >= 1       # at least 1 variable of x must take the value 1
AtLeastOne(x, value=1)       # (equivalent form)

Count(x, value=0) <= 1       # at most 1 variable of x must take the value 0
AtMostOne(x, value=0)        # (equivalent form)

Count(x, value=1) == 1       # exactly 1 variable of x must take the value 1
ExactlyOne(x, value=1)       # (equivalent form)

Count(x, value=1) == v       # the count must be equal to the value of v
Count(x, values=[1,2]) == 3  # excatly 3 variables must take their values in {1, 2}

Count([x[0]+x[1], x[1]+x[2], x[2]+x[3]], value=3) == 2  # with expressions

Exist(x[i] != y[i] for i in range(n))     # at least one expression must evaluate to 1 (true)
NotExist(x[i] != y[i] for i in range(n))  # none expression must evaluate to 1 
AllHold(x[i] != y[i] for i in range(n))   # all expressions must evaluate to 1

Hamming(x, y) > 3                         # the Hamming distance must be greater than 3 

Cumulative

The cumulated height of some tasks must respect a numerical condition; this for each time point when considering the tasks that overlap that point.

x = VarArray(size=5, dom=range(8))
lengths = [3,2,2,4,2]
heights = [3,2,2,2,3]

Cumulative(origins=x, lengths=lengths, heights=heights) <= 5
Cumulative(tasks=[(x[i],lengths[i],heights[i]) for i in range(5)]) <= 5
Cumulative(Task(origin=x[i],length=lengths[i],height=heights[i]) for i in range(5)) <= 5

Cumulative(
  tasks=[Task(origin=x[i],length=lengths[i],height=heights[i]) for i in range(5)]
) <= 5      

Decreasing / Increasing

The values assigned to the variables of a list must be in decreasing (resp. increasing) order.

[x[i] >= x[i+1] for i in range(n-1)]  # values in x (array of size n) are in decreasing order
Decreasing(x)                         # equivalent form

[x[i] + t[i] < x[i+1] for i in range(n-1)]   # constants from a list t are considered 
Increasing(x, lengths=t, strict=True)        # equivalent form

Element

The element of a list of variables (or integers) at a specified index given by a variable (of the model) must respect a numerical condition. A variant exists for two-dimensional lists (matrices) by using two indexes.

x[v] >= 1      # v is a variable (of the model)
x[v] == w      

m[v][w] == 0   # m is a two-dimensional lists

Extension (Table)

A constraint Extension (or table constraint) enumerates the tuples of values that are allowed or forbidden for a sequence of variables.

x = VarArray(size=4, dom={1,2,3})

x[0] in {1,3}       # unary positive constraint (allowed values) 
x[2] not in {2,3}   # unary negative constraint (forbidden values)

x in {(1,2,3,2), (2,1,1,2), (2,3,2,1), (3,1,2,3)}                 # ordinary positive table
(x[3],x[1],x[0],x[2]) not in {(1,2,3,2), (2,1,1,2), (3,1,2,3)}    # ordinary negative table 
(x[0],x[1],x[2]) in {(1,ANY,2), (2,1,ANY), (3,1,3)}               # starred table 

Intension

A constraint Intension corresponds to a Boolean expression that may involve variables, constants and various (arithmetic, relational and logical) operators.

v + w < 10
abs(x[0 - x[1]) >= 7

(v < 2) | (w == 4)     # use of the logical operator 'or' with '|'
either(v < 2, w == 4)  # (equivalent form)

(v < 2) & (w == 4)     # use of the logical operator 'and' with '&'
both(v < 2, w == 4)  # (equivalent form)

Knapsack

Some items must be packed in a knapsack with certain weight and profit restrictions; each item is associated with 2 attributes: its weight and its profit.

x = VarArray(size=5, dom={0, 1})     # 5 possible items to be put in the knapsack

Knapsack(x, weights=[4,8,3,5,7], wlimit=20, profits=[2,3,4,4,3]) >= 12           # with a weight condition '<= 20'
Knapsack(x, weights=[4,8,3,5,7], wcondition=lt(20), profits=[2,3,4,4,3])) >= 12  # with a weight condition '< 20'

Lex

The sequence of values assigned to a list of variables must be lexicographically less than (resp, greater than) the sequence of values assigned to a second list of variables.

LexIncreasing(x,y)                  # x is less than or equal to y 
LexIncreasing(x, y, strict=True)    # x is strictly less than y

LexDecreasing(x, y, z, strict=True) # x is greater than or equal to y, itself greater than or eqaul to z 
LexDecreasing(m, matrix=True)       # all rows are lexicographically ordered as well as all columns

MDD

The (sequence of) values assigned to the variables of a list must correspond to a path going from the root of a specified MDD (Multi-valued Decision Diagram) to its (unique) terminal node.

r, n1, n2, n3, n4, n5, t = "r", "n1", "n2", "n3", "n4", "n5", "t"  # names of nodes
transitions = [(r,0,n1), (r,1,n2), (r,2,n3), (n1,2,n4), (n2,2,n4), (n3,0,n5), (n4,0,t), (n5,0,t)]
M = MDD(transitions)

(x[0],x[1],x[2]) in M   # values assigned to variables in x must correspond to a path in the MDD M 

Maximum / Minimum

The maximum (resp. minimum) value in a list of variables (or expressions) must respect a numerical condition.

Maximum(x) > 1          # the maximum value in x must be greater than 1
Minimum(x) == v         # the value of v corresponds to the minimum value in x

Maximum(x[0]+x[1], x[1]+x[2], x[2]+x[3]) >= 5   # when using expressions

NValues

The number of distinct values in a list of variables (or expressions) must respect a numerical condition.

NValues(x) <= 2  # the number of distinct values assigned to variables in x must be less or equal to 2
NValues(x) == v  # the number of distinct values assigned to variables in x is equal to the value of v

NValues(x[0]+x[1], x[1]+x[2], x[2]+x[3], x[3]+x[4]) > 2  # when using expressions 

NoOverlap

One dimensional: some objects (e.g., tasks), defined by their origins (e.g., starting times) and lengths (e.g., durations), must not overlap. </br> Multi-dimensional: some objects of multi-dimensional form must not overlap., i.e., there must exist at least one dimension where one box is after the other.

NoOverlap(origins=x, lengths=[3,5,2,4])                      # one-dimensional form
NoOverlap(origins=x, lengths=y)

NoOverlap(origins=m1, lengths=[[5,4], [2,3], [3,2], [3,4]])  # two-dimensional form
NoOverlap(origins=m1, lengths=m2)

Precedence

If a variable v of a list x of variables is assigned the i+1th value of a list t of values, then another variable preceding v in x, must be assigned the ith value of t.

Precedence(x, values=[0,1])   # if 1 is assigned, 0 must be assigned before by another variable of x.
Precedence(x)                 # (the property must hold when considering the ordered set of possible values)

Regular

The (sequence of) values assigned to the variables of a list must belong to a regular language specified by an automaton (i.e., forms a word that can be recognized by a deterministic, or non-deterministic, finite automaton).

a, b, c, d, e = "a", "b", "c", "d", "e"  # names of states
t = [(a,0,a), (a,1,b), (b,1,c), (c,0,d), (d,0,d), (d,1,e), (e,0,e)]
A = Automaton(start=a, transitions=t, final=e)

x in A   # the tuple/word formed by values assigned to variables in x must be accepted by Automaton A 

Sum

A sum of variables or expressions must respect a numerical condition.

Sum(x) == 12                             # simple sum

Sum(x[i] * c[i] for i in range(5)) > 28  # weighted sum
x * c  > 28                              # equivalent form (dot product) 

Sum(x[i] >= 2 for i in range(4))  >= 3   # sum of expressions

5) Specifying an objective

It is possible to maximize or to minimize an objective. Here are some examples that corresponds to minimizing:

minimize(v)                        # the value of the (single) variable v
minimize(v + w * 10)               # the value of an expression
minimize(Sum(x))                   # the sum of x
minimize([v, w] * [3, 2])          # a dot product
minimize(Minimum(x))               # the minimum value in x
minimize(Maximum(x))               # the maximum value in x
minimize(NValues(x))               # the number of different values in x
minimize(Sum(x) - Maximum(y) * 3)  # the value of a complex expression