วันพฤหัสบดีที่ 20 มีนาคม พ.ศ. 2551

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)
);

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.