Example: Family

This example also illustrates the use of symmetry elimination and defined constraints.

Problem Specification

Maria and Clara are both heads of households, and both families have three boys and three girls. Neither family includes any children closer in age than one year, and all children are under age 10. The youngest child in Maria's family is a girl, and Clara has just given birth to a little girl.

In each family, the sum of the ages of the boys equals the sum of the ages of the girls, and the sum of the squares of the ages of the boys equals the sum of the the squares of ages of the girls. The sum of the ages of all children is 60.

What are the ages of the children in each family?

Viewpoint

The viewpoint of this problem consists of 12 variables and each of these variables is associated with the domain of the integers 0, ..., 9. We model a family as a record

{boys:#[B1 B2 B3], girls:#[G1 G2 G3]}

where the variables B1, B2 and B3 stand for the ages of the boys in descending order (i. e., B3 is the age of the youngest boy in the family), and the variables G1, G2 and G3 stand for the ages of the girls, also in descending order. This representation of a family avoids possible symmetries. The constraints that must hold for a family will be posted by the defined constraint makefamily. A solution is a pair consisting of Maria's and Clara's family.

Branching Stratgey

We branch on the list of the ages of the children of the two families following a first-fail strategy. The strategy splits the domain of the selected variable and tries the lower part of the domain first.

Script

fun age_list space =
    let
        val ages as #[a,b,c] = FD.intvarVec(space,3,#[(0,9)])
    in 
        FD.rel(space,a,FD.GR,b);
        FD.rel(space,b,FD.GR,c);
        ages
    end

fun makefamily space =
    let
        val boysages  = age_list space
        val girlsages = age_list space
        val tmp1 = FD.range(space,(0,243))
        val tmp2 = FD.range(space,(0,243))
        val ages as #[a,b,c,d,e,f] = 
                Vector.concat([boysages,girlsages])
        fun squares_sum(#[x,y,z],res)= 
            post(space,FD(x)`* FD(x)`+ 
                       FD(y)`* FD(y)`+
                       FD(z)`* FD(z) `= FD(res),FD.DOM)
    in
        FD.distinct(space,ages,FD.DOM);
        post(space,FD(a) `+ FD(b) `+ FD(c) 
                `= FD(d) `+ FD(e) `+ FD(f),FD.DOM);
        squares_sum(boysages,tmp1);
        squares_sum(girlsages,tmp2);
        FD.rel(space,tmp1,FD.EQ,tmp2);
        {boys= #[Vector.sub(ages,0),Vector.sub(ages,1),
                 Vector.sub(ages,2)],
         girls = #[Vector.sub(ages,3),Vector.sub(ages,4),
                   Vector.sub(ages,5)]}
    end

fun family space = 
    let
        val maria = makefamily space
        val clara = makefamily space
        val ageofmariasyoungestgirl = Vector.sub(#girls maria,2)
        val ageofclarasyoungestgirl = Vector.sub(#girls clara,2)
        val ages = Vector.concat([#boys (maria),#girls (maria),
                                  #boys(clara),#girls(clara)])
    in
        Vector.app(fn x => 
              FD.rel(space,x,FD.GR,ageofmariasyoungestgirl))
                  (#boys maria);
        FD.relI(space,ageofclarasyoungestgirl,FD.EQ,0);
        post(space,SUMV(ages) `= `60,FD.DOM);
        FD.branch(space,ages,FD.B_SIZE_MIN,FD.B_MIN);
        {maria,clara}
    end

The procedure age_list ensures that the elements in the list of boys or girls appear in descending order.