
Toni Mancini, Davide Micaletto, Fabio Patrizi, Marco Cadoli
Dipartimento di Informatica e Sistemistica
Università di Roma "La Sapienza"
via Salaria 113, I00198 Roma, Italy
Appeared in
Constraints, 13(4), pages 407436, 2008.
Web appendix
Modelling languages and solvers used
We present the output of our modelling task on 9 problems from the CSPLib in the following languages:
 The algebraic (Existential SO logiclike) language OPL, input language for the following solver(s):
 The rulebased language DLV, input language for the following solver(s):
 The rulebased language LPARSE, input language for the following solver(s):
Problems considered
Given a positive integer 'n_marks', this problem amounts to put 'n_marks' marks on a ruler, in such a way that the n_marks(n_marks  1)/2 distances among them are all different. The objective is to find the length of the shortest ruler that admits the positioning of 'n_marks' marks.Given the twelve standard pitchclasses (c, c#, d, ...), represented by numbers 0,1,...,11, this
problem amounts to find a series in which each pitchclass occurs exactly once
and in which the musical intervals between neighboring notes cover the full
set of intervals from the minor second (1 semitone) to the major seventh (11
semitones). That is, for each of the intervals, there is a pair of neighboring
pitchclasses in the series, between which this interval appears. We consider a generalization of this problem in which the set of numbers is
the range from 0 to n1, for any given positive 'n'. In particular, given such 'n',
the problem amounts to find a vector s = (s1, ..., sn) that is a permutation of {0, 1,..., n1} and such that the interval vector v = (s2  s1, s3  s2, ..., sn  s(n1)) is a permutation of {1, 2,..., n1}. In a golf club there are 32 social golfers who play once a week in 8 groups of 4. The problem amounts to find a schedule for as many as possible weeks, such that no two golfers play in the same group more than once. Here we consider the decisional version of the problem (wrt the number of weeks 'weeks'), where the number of players and the group size are given as input. The problem amounts to color the edges of a complete graph with n nodes using the minimum number of colors, in such a way that there is no
monochromatic triangle in the graph, i.e. in any triangle at most two edges have the same color.This is a generalization of the CSPLib specification, which is
as follows: Given an 8 pint bucket of water, and two empty buckets which can
contain 5 and 3 pints respectively, the problem requires to divide the water
into two by pouring water between buckets (that is, to end up with 4 pints in
the 8 pint bucket, and 4 pints in the 5 pint bucket) in the smallest number of
transfers. The generalization consists in making the specification parametric with respect
to the start and goal configurations, which are now inputs to the problem. An order 'n' magic
square is a 'n' by 'n' matrix containing the numbers 1 to n^{2}, with each row, column
and main diagonal equal the same sum.
Given a positive integer 'n', the problem
amounts to find a 'n' order magic square.This is a generalization of the specification given in the CSPLib (which fixes the forthcoming value 'n' to 4). Given two sets of the numbers from 1 to n, the problem amounts
to arrange the 2n numbers in the two sets into a single sequence in which the two 1's appear one number apart, the two 2's appear two numbers apart, the two 3's appear three numbers apart,... , and the two n's appear n numbers apart.Life is played on a squared board, considered
to extend to infinity in all directions. Each square of the board is a cell, which at any time during the game is either alive or dead. A cell has eight neighbours. The configuration of live and dead cells at time t leads to a new configuration
at time t + 1 according to the rules of the game:
 If a cell has exactly three living neighbours at time t, it is alive at time t + 1;
 If a cell has exactly two living neighbours at time t, it is in the same state at time t + 1 as it was at time t;
 Otherwise, the cell is dead at time t + 1.
A stable pattern, or stilllife, is not changed by these rules. Hence, every cell that has exactly three live neighbours is alive, and every cell that has fewer than two or more than three live neighbours is dead. (An empty board is a stilllife, for instance.) Given a positive integer n, the problem amounts to find the densest possible stilllife pattern, i.e. the pattern with the largest number of live cells, that can be fitted into an n by n section of the board, with all the rest of the board dead. The problem amounts to find as large a set S of strings (words) of length 8 over the alphabet W = {A,C,G,T} with the following properties:
 Each word in S has 4 symbols from {C,G};
 Each pair of distinct words in S differ in at least 4 positions;
 Each pair of words x and y in S (where x and y may be identical) are such that R(x) and C(y) differ in at least 4 positions.
Here, R(x1,...,x8) = x8,...,x1 is the reverse of x1,...,x8 and C(y1,...,y8) is the WatsonCrick complement of y1,...,y8, i.e. the word where
each A is replaced by a T and vice versa and each C is replaced by a G and vice versa.
Here we consider a decisional version of the problem: given integer nbwords, the problem amounts to find a set of nbwords words with the above properties.
