7.4 Exercises

Exercise 7.1 (See solution)

Magic Sequence

A magic sequence of length n is a sequence


of integers such that for every i=0,\ldots,n-1

  • x_i is an integer between 0 and n-1.

  • the number i occurs exactly x_i times in the sequence.

Write a parameterized script that, given n, can enumerate all magic sequences of length n.

The script should use the procedure

{FD.exactly K S I}

that creates a propagator for the constraint saying that exactly K fields of the record S are equal to the integer I.

You can drastically reduce the search space of the script by having propagators for the redundant constraints



(-1)\cdot x_0\;+\;\ldots\;+\;(n-2)\cdot

Explain why these constraints are redundant.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)