Example: Zebra Puzzle

This example also illustrates the use of defined constraints and shows a clever problem representation avoiding possible symmetries.

Problem Specification

Five men with different nationalities live in the first five houses of a street. There are only houses on one side of the street. The men practice distinct professions, and each of them has a favorite drink and a favorite animal, all of them different. The five houses are painted with different colors. The following facts are known:

1. The Englishman lives in a red house.
2. The Spaniard owns a dog.
3. The Japanese is a painter.
4. The Italian drinks tea.
5. The Norwegian lives in the first house.
6. The owner of the green house drinks coffee.
7. The green house comes after the white one.
8. The sculptor breeds snails.
9. The diplomat lives in the yellow house.
10. Milk is drunk in the third house.
11. The Norwegian's house is next to the blue one.
12. The violinist drinks juice.
13. The fox is in the house next to that of the doctor.
14. The horse is in the house next to that of the diplomat.
15. The zebra is in the white house.
16. One of the men drinks water.

Who lives where?

Viewpoint

For this problem a viewpoint is choosen consisting in 25 finite domain variables, each associated with the domain {1,..., 5}. We number the houses from 1 to 5, where 1 is the first and 5 is last house in the street. There are 25 different properties (i. e. hosting an Englishman, being the green house, hosting a painter, hosting a dog, or hosting someone who drinks juice), and each of these properties must hold for exactly one house. The properties are partitioned into five groups of five members each, where the properties within one group must hold for different houses. The model has one variable for each of these properties, where the variable stands for the number of the house for which this property holds.

Branching Strategy

We branch on the variables for the properties with the standard first-fail strategy.

Script

The defined constraint adjacent in Listing 6 creates a propagator for | X - Y | = 1.

fun adjacent (space,#[a,b])=
        let
           val tmp = FD.range(space,(~4,4))
           val one = FD.range(space,(1,1))
        in
           post(space,FD(a) `- FD(b) `= FD(tmp),FD.DOM);
           FD.abs(space,tmp,one,FD.DOM)
        end


   
fun zebra_puzzle space =
  let
     val nationality  = 
       {engl=FD.range(space,(0,4)),span=FD.range(space,(0,4)),
        jap=FD.range(space,(0,4)),ital=FD.range(space,(0,4)),
        norw=FD.range(space,(0,4))}
     val color  =
       {green=FD.range(space,(0,4)),red=FD.range(space,(0,4)),
        yellow=FD.range(space,(0,4)),blue=FD.range(space,(0,4)),
        white=FD.range(space,(0,4))}
     val profession = 
       {painter =FD.range(space,(0,4)),diplomat=FD.range(space,(0,4)),
        violinist =FD.range(space,(0,4)),doctor=FD.range(space,(0,4)),
        sculptor=FD.range(space,(0,4))}
     val animal =
       {dog=FD.range(space,(0,4)),zebra=FD.range(space,(0,4)),
        fox=FD.range(space,(0,4)),snails=FD.range(space,(0,4)),
        horse=FD.range(space,(0,4))}
     val drink  = 
       {juice=FD.range(space,(0,4)),water=FD.range(space,(0,4)),
        tea=FD.range(space,(0,4)),coffee=FD.range(space,(0,4)),
        milk=FD.range(space,(0,4))}
     fun makevector() = 
        let val a = (fn x => #[#engl(x),#ital(x),#jap(x),#norw(x),
                        #span(x)])nationality
            val b = (fn x => #[#green(x),#red(x),#yellow(x),#blue(x),
                        #white(x)])color
            val c = (fn x => #[#painter(x),#diplomat(x),#violinist(x),
                        #doctor(x),#sculptor(x)])profession
            val d = (fn x => #[#dog(x),#zebra(x),#fox(x),#snails(x),
                        #horse(x)])animal
            val e = (fn x => #[#juice(x),#water(x),#tea(x),#coffee(x),
                        #milk(x)])drink
        in
            #[a,b,c,d,e]
        end
     val varvec = makevector()
  in
        (* the following constraint ensures that the properties
           within one group hold for different houses*) 
        Vector.app(fn x => FD.distinct(space,x,FD.BND))
                      varvec;          
        (* the next 15 constraints ensure the known
           facts mentioned in the problem specification *)
        FD.rel(space,#engl(nationality),FD.EQ,#red(color));
        FD.rel(space,#dog(animal),FD.EQ,#span(nationality));
        FD.rel(space,#painter(profession),FD.EQ,#jap(nationality));
        FD.rel(space,#tea(drink),FD.EQ,#ital(nationality));
        FD.relI(space,#norw(nationality),FD.EQ,0);
        FD.rel(space,#green(color),FD.EQ,#coffee(drink));
        FD.rel(space,#green(color),FD.GR,#white(color));
        FD.rel(space,#sculptor(profession),FD.EQ,#snails(animal));
        FD.rel(space,#diplomat(profession),FD.EQ,#yellow(color));
        FD.relI(space,#milk(drink),FD.EQ,2);
        adjacent(space,#[#norw(nationality),#blue(color)]);
        FD.rel(space,#violinist(profession),FD.EQ,#juice(drink));
        adjacent(space,#[#fox(animal),#doctor(profession)]);
        adjacent(space,#[#horse(animal),#diplomat(profession)]);
        FD.rel(space,#zebra(animal),FD.EQ,#white(color));
        
        FD.branch(space,Vector.concat(Vector.toList(varvec)),
                   FD.B_SIZE_MIN,FD.B_MIN);
        {nationality,color,profession,animal,drink}
 end

The script defines a search tree with 29 nodes. The unique solution is the record
{animal = {dog = 2, fox = 4, horse = 3, snails = 1, zebra = 0},
color = {blue = 1, green = 4, red = 3, white = 0, yellow = 2},
drink = {coffee = 4, juice = 0, milk = 2, tea = 1, water = 3},
nationality = {engl = 3, ital = 1, jap = 4, norw = 0, span = 2},
profession = {diplomat = 2, doctor = 3, painter = 4, sculptor = 1, violinist = 0}}