14. Magic sequence¶
This chapter shows how to use counting constraints for solving magic sequence puzzles.
14.1. Problem¶
The Magic Sequence puzzle ( CSPLib problem 19 , first introduced as a constraint problem in [70] ) requires finding a sequence of integers \(x_0,\dots,x_{n-1}\) such that for all \(0\leq i< n\), the number \(i\) occurs exactly \(x_i\) times in the sequence. For example, a magic sequence of length \(n=8\) is
14.2. Model¶
The outline of the script for solving magic sequence puzzles is shown in A script for solving magic sequence puzzles . It contains the integer variable array x (see Integer and Boolean variable arrays ), which is initialized according to the problem specification.
...
class MagicSequence : public Script {
IntVarArray x;
public:
MagicSequence(const SizeOptions& opt)
: Script(opt), x(*this,opt.size(),0,opt.size()-1) {
// [magic sequence:counting constraints]
// [magic sequence:implied constraints]
// [magic sequence:branching]
}
...
};
...
Download: magic-sequence.cpp
14.2.1. Counting constraints.¶
The problem can be modeled directly using one counting constraint (see Counting constraints ) per variable. We will see later that there is a global constraint that combines all these individual counting constraints.
for (int i=0; i<x.size(); i++)
count(*this, x, i, IRT_EQ, x[i]);
14.2.2. Implied linear constraints.¶
The model as described so far completely captures the problem. Therefore, given enough time, Gecode will return all its solutions and only the solutions. However, it is sometimes useful to post additional, implied constraints, which do not change the meaning of the model (they do not change the set of solutions), but which provide additional constraint propagation that results in a smaller search tree.
The two implied constraints that we will use for the magic sequence problem result from the fact that any magic sequence of length \(n\) satisfies the following two equations:
The first equation is true because the sum of all occurrences, i.e. the overall number of items in the sequence, must be equal to the length of the sequence.
The second equation can be rewritten as
So it remains to be shown that \(\sum_{i=0}^{n-1}i\cdot \mathtt{x}_i\) is also equal to the length of the sequence. This follows from the fact that \(\mathtt{x}_i\) is the number of times \(i\) occurs in the sequence, so \(i\cdot \mathtt{x}_i\) is the number of positions occupied by the sequence elements that are equal to \(i\), and the sum over those must be equal to the length of the sequence.
The two equations translate easily into linear constraints (see Linear constraints ), using integer argument arrays of type IntArgs (see Argument arrays ) to supply coefficients.
linear(*this, x, IRT_EQ, x.size());
linear(*this, IntArgs::create(x.size(),-1,1), x, IRT_EQ, 0);
You can do your own experiments, comparing runtime and search tree size of the model with and without implied constraints.
14.2.3. Branching.¶
For large sequences, many variables in the sequence will be \(0\) because the overall sum is only \(n\) (see previous paragraph on implied constraints). Therefore, \(\mathtt{x}_0\) should take a large value. We simply branch in the given order of the variables, starting with the largest values.
branch(*this, x, INT_VAR_NONE(), INT_VAL_MAX());
14.2.4. Global counting constraints.¶
The global counting constraint (also known as global cardinality constraint, see Counting constraints ) can express the combination of all the individual counting constraints, and yields stronger propagation. It also includes the propagation of the first of the two implied linear constraints. So, as an alternative to the \(n\) counting constraints above, we can use the code in Magic sequence puzzles with a global counting constraint .
14.3. More information¶
The magic sequence puzzle is also included as a Gecode example, see magic-sequence . The example contains both the model using individual counting constraints and the one using a single global counting constraint.
...
class MagicSequence : public Script {
IntVarArray x;
public:
MagicSequence(const SizeOptions& opt)
: Script(opt), x(*this,opt.size(),0,opt.size()-1) {
// Global counting constraint
count(*this, x, x, opt.ipl());
// Implied constraint
linear(*this, IntArgs::create(x.size(),-1,1), x, IRT_EQ, 0);
// Branching
branch(*this, x, INT_VAR_NONE(), INT_VAL_MAX());
}
...
};
...
Download: magic-sequence-gcc.cpp