Constraint Programming Part V - Einstein's Puzzle

There are 5 houses, which each house is different colors, different nationalities, different pets, different drinks, and different cigarettes.

And here are the constraints

• The British lives in the red house.
• The Swedish keeps dogs as pets.
• The Danish drinks tea.
• The green house is on the left of the white house.
• The green homeowner drinks coffee.
• The person who smokes Pall Mall rears birds.
• The owner of the yellow house smokes Dunhill.
• The man living in the center house drinks milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives next to the one who keeps cats.
• The man who keeps the horse lives next to the man who smokes Dunhill.
• The owner who smokes Bluemaster drinks beer.
• The German smokes prince.
• The Norwegian lives next to the blue house.
• The man who smokes Blend has a neighbor who drinks water.

Question is who own the fish?

You can try to solve yourself. Only 2% of people can solve this puzzle.

For solving by constraint programming, first, is to create the types.

public enum Nationality {
    British,
    Swedish,
    Danish,
    Norwegian,
    German,
}
public enum HouseColor {
    Red,
    Green,
    White,
    Yellow,
    Blue,
}
public enum Smoke {
    PallMall,
    DunHill,
    Blend,
    BlueMaster,
    Prince,
}
public enum Drink {
    Tea,
    Coffee,
    Milk,
    Beer,
    Water,
}
public enum Pet {
    Dog,
    Bird,
    Cat,
    Horse,
    Fish,
}

Then we split questions into 2 groups. First group is questions about properties of a single house. Second group is questions about properties between houses.

Here is the first group of questions.

- The British lives in the red house.
- The Swedish keeps dogs as pets.
- The Danish drinks tea.
- The green homeowner drinks coffee.
- The person who smokes Pall Mall rears birds.
- The owner of the yellow house smokes Dunhill.
- The owner who smokes Bluemaster drinks beer.
- The German smokes prince.

You can solve above properties by using linq.

var men = from n in Enumerable2.Enum<Nationality>()
          from c in Enumerable2.Enum<HouseColor>()
          where (n == Nationality.British) == (c == HouseColor.Red)
          from s in Enumerable2.Enum<Smoke>()
          where (n == Nationality.German) == (s == Smoke.Prince)
          where (c == HouseColor.Yellow) == (s == Smoke.DunHill)
          from d in Enumerable2.Enum<Drink>()
          where (n == Nationality.Danish) == (d == Drink.Tea)
          where (c == HouseColor.Green) == (d == Drink.Coffee)
          where (s == Smoke.BlueMaster) == (d == Drink.Beer)
          from p in Enumerable2.Enum<Pet>()
          where (n == Nationality.Swedish) == (p == Pet.Dog)
          where (s == Smoke.PallMall) == (p == Pet.Bird)
          select new {
              Nationality = n,
              HouseColor = c,
              Smoke = s,
              Drink = d,
              Pet = p
          };

By using above expression 5^5 combinations of properties are reduced to only 78 combinations of properties. You can get Count by

Console.WriteLine(men.Count());
//78

And for remaining constraints can be solved by Arranger class.

//Generate solution
var solutions = men.Arrange(5);

//New guy must not has same properties as persons in sequence
solutions.AppendConstraint(seq => seq.Any(),
    seq => man => seq.All(x =>
        x.Nationality != man.Nationality &&
        x.HouseColor != man.HouseColor &&
        x.Smoke != man.Smoke &&
        x.Drink != man.Drink &&
        x.Pet != man.Pet
    )
);

//Norwegian lives in the first house.
solutions.AppendConstraint(seq => seq.Length == 0,
    seq => man => man.Nationality == Nationality.Norwegian
);

//Guy who drinks milk lives in the third house
solutions.AppendConstraint(seq => seq.Length <= 2,
    seq => man => (seq.Length == 2) == (man.Drink == Drink.Milk)
);

//White house is next to green house
solutions.AppendConstraint(seq => seq.Any(),
    seq => man => (seq.Last().HouseColor == HouseColor.Green) == (man.HouseColor == HouseColor.White)
);

//Guy who pets cat is neighbor with guy who smokes Blend
solutions.AppendConstraint(seq => seq.Count(x => x.Pet == Pet.Cat || x.Smoke == Smoke.Blend) == 1,
    seq => man => (man.Pet == Pet.Cat) || (man.Smoke == Smoke.Blend)
);

//Guy who pets horse is neighbor with guy who smokes DunHill
solutions.AppendConstraint(seq => seq.Count(x => x.Pet == Pet.Horse || x.Smoke == Smoke.DunHill) == 1,
    seq => man => (man.Pet == Pet.Horse) || (man.Smoke == Smoke.DunHill)
);

//Norwegian is neighbor with guy lives in blue house
solutions.AppendConstraint(seq => seq.Count(x => x.Nationality == Nationality.Norwegian || x.HouseColor == HouseColor.Blue) == 1,
    seq => man => (man.Nationality == Nationality.Norwegian) || (man.HouseColor == HouseColor.Blue)
);

//Guy who drinks water is neighbor with guy who smokes Blend
solutions.AppendConstraint(seq => seq.Count(x => x.Drink == Drink.Water || x.Smoke == Smoke.Blend) == 1,
    seq => man => (man.Drink == Drink.Water) || (man.Smoke == Smoke.Blend)
);

And this is the answer.

solutions.First().ForEach(Console.WriteLine);
//{ Nationality = Norwegian, HouseColor = Yellow, Smoke = DunHill, Drink = Water, Pet = Cat }
//{ Nationality = Danish, HouseColor = Blue, Smoke = Blend, Drink = Tea, Pet = Horse }
//{ Nationality = British, HouseColor = Red, Smoke = PallMall, Drink = Milk, Pet = Bird }
//{ Nationality = German, HouseColor = Green, Smoke = Prince, Drink = Coffee, Pet = Fish }
//{ Nationality = Swedish, HouseColor = White, Smoke = BlueMaster, Drink = Beer, Pet = Dog }

Next is last part of constraint programming. We will learn to use Arranger class to solve questions with unknown length of solution. The question is river crossing.