8.2 Example: Aligning for a Photo

We will now see an overconstrained problem for which it is impossible to satisfy all constraints. The problem specification will distinguish between primary and secondary constraints, and the goal is to find a solution that satisfies all primary constraints and as many of the secondary constraints as possible.

Problem Specification

Betty, Chris, Donald, Fred, Gary, Mary, and Paul want to align in one row for taking a photo. Some of them have preferences next to whom they want to stand:

  1. Betty wants to stand next to Gary and Mary.

  2. Chris wants to stand next to Betty and Gary.

  3. Fred wants to stand next to Mary and Donald.

  4. Paul wants to stand next to Fred and Donald.

Obviously, it is impossible to satisfy all preferences. Can you find an alignment that maximizes the number of satisfied preferences?


The model has a variable A_p for every person, where A_p stands for the position p takes in the alignment. Since there are exactly 7 persons, we have A_p\in 1\#7 for every person p. Moreover, we have A_p\neq A_q for every pair p,q of distinct persons. The model has a variable S_i\in0\#1 for each of the 8 preferences, where S_i=1 if and only if the i-th preference is satisfied. To express this constraint, we constrain the control variable S of a preference ``person p wants to stand next to person q'' by means of the reified constraint


Finally, there is a variable

{\it Satisfaction} \;=\; S_1\;+\;\ldots\;+\;S_8

denoting the number of satisfied preferences. We want to find a solution that maximizes the value of {\it Satisfaction}.

The experienced constraint programmer will note that we can eliminate a symmetry by picking two persons p and q and imposing the order constraint A_p<A_q.

Distribution Strategy.

To maximize {\it Satisfaction}, we employ a two-dimensional distribution strategy, which first distributes on {\it Satisfaction}, trying the values 8,\,7,\,\ldots\,1 in this order. Once {\it Satisfaction} is determined, we distribute on the variables A_p using a first-fail strategy that splits the domain of the selected variable.


proc {Photo Root}
   Persons       = [betty chris donald fred gary mary paul]
   Preferences   = [betty#gary betty#mary  chris#betty chris#gary
                    fred#mary  fred#donald paul#fred   paul#donald]
   NbPersons     = {Length Persons}
   Alignment     = {FD.record alignment Persons 1#NbPersons}
   Satisfaction  = {FD.decl}  
   proc {Satisfied P#Q S}
      {FD.reified.distance Alignment.P Alignment.'=:' 1 S}
   Root = r(satisfaction: Satisfaction
            alignment:    Alignment)
   {FD.distinct Alignment}
   {FD.sum {Map Preferences Satisfied} '=:' Satisfaction}
   Alignment.fred <: Alignment.betty     % breaking symmetries
   {FD.distribute generic(order:naive value:max) [Satisfaction]}
   {FD.distribute split Alignment}

Figure 8.1: A script for the Photo Puzzle.

The script in Figure 8.1 constrains its root variable to a record consisting of the number of satisfied preferences and a record mapping the names of the persons to their positions in the alignment. The fields of the record Alignment implement the variables A_p of the model.


The script introduces the defined constraint {Satisfied P#Q S}, which implements the reification of the constraint ``P stands next to Q'' with respect to S.

The statement

{FD.sum {Map Preferences Satisfied} '=:' Satisfaction}

constrains the variable Satisfaction to the number of satisfied preferences.

The statement {ExploreOne Photo} will run the script until a first solution is found. The first solution satisfies 6 preferences and looks as follows:

# alignment(betty:5  chris:6  donald:1  fred:3  
              gary:7   mary:4   paul:2)

By construction of the script, this is the maximal number of preferences that can be satisfied simultaneously.


Exercise 8.3 (See solution)

Modify the script such that the first solution minimizes the number of preferences satisfied.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)