Constraint Programming Part VI - River Crossing

River crossing is a puzzle, which its objective is to bring all people (father, mother, 2 sons, 2 daughters, police, and thief) crossing a river. With the constriants that:

- Not more than 2 persons can raft at a time
- Father cannot stay with daughter without mother
- Mother cannot stay with son without father
- Thief cannot stay with any body without police
- Only father, mother, and police can raft

You can play online game here.

To solve this puzzle with arranger class, first, let's declare the members.

[Flags]
public enum Cross {
    Thief = 1,
    Police = 2,
    Father = 4,
    Mother = 8,
    Son = 16,
    Son2 = 32,
    Daughter = 64,
    Daughter2 = 128,
}

Cross type is flag because, we want to consolidate any combinations of persons into a variable. We can declare allPeople represents all persons in Cross type.

var allPeople = Cross.Thief | Cross.Police | Cross.Father | Cross.Mother | Cross.Son | Cross.Son2 | Cross.Daughter | Cross.Daughter2;

And below function is to switch the presence of persons in combination.

Func<Cross, Cross> opp = x => x ^ allPeople;

To solve this puzzle, we might divid problem into 2 steps, combination of persons of each crossing, and combination of crossing which can solve the puzzle.

We can declare custom construction of Arranger class by using command e.Arrange(arg1, arg2, arg3). Where e is enumerable. Arg1 is local variable, if you need more than 1 variable, you can combine variables into an anonymous type new {var1, var2}. Arg2 is assignment of new local variable when a new member is added. Arg3 is condition to complete the solution.

To create Arranger class, represents combination of persons of each crossing:

var crossing = Enumerable2.Enum<Cross>().Arrange(

    //Seed - number of people, and people
    new { Length = 0, Value = (Cross)0 },

    //Func - add number of people, add people
    (current, item, i) => new { Length = current.Length + 1, Value = current.Value | item },

    //Yield - must contains police, father, or mother
    current => (current.Value & (Cross.Police | Cross.Father | Cross.Mother)) > 0
);

This is custom construction of Arranger class. Arg1 (local variable) is anonymous type of length (number of person) and value (combination of persons). Arg2 (assignment of local variable), current is variable before adding new member, item is new member, and i is index of new member. When new member is added, length is increased by 1, and value is included new member. Arg3, solution will be completed when value contains father, or mother, or police.

The Arranger class is not finished yet. We must add constraints to the class.

//no police-police, and police-thief is the same as thief-police
crossing.ArrangementModel = ArrangementModel.Combination;

//Answer can be 1 or 2 people on boat
crossing.ContinueOnYielded = true;

//Stop arranging when there are more than 2 people
crossing.AppendBreak(current => current.Length > 2);

//Thief must be with police
crossing.AppendConstraint(current => current.Value == Cross.Thief, current => item => item == Cross.Police);

//Father cannot be with daughter
crossing.AppendConstraint(current => current.Value == Cross.Father, current => item => item != Cross.Daughter && item != Cross.Daughter2);

//Mother cannot be with son
crossing.AppendConstraint(current => current.Value == Cross.Mother, current => item => item != Cross.Son && item != Cross.Son2);

This arrangement model is combination because, we don't care the position of persons in raft, "police-thief" is considered the same as "thief-police". And we cannot repeat a person in raft, such as "police-police" is impossible.

ContinueOnYield is the command to search more members when found a solution. Such as solutions to cross can be either "police", or "police-thief".

AppendBreak is command to stop searching. Above, we stop searching when number of members to cross is more than 2.

You can list all possible crossing combination.

crossing.SelectResults(c => c.Value).ForEach(c => Console.WriteLine(c));
//Thief, Police
//Police
//Police, Father
//Police, Mother
//Police, Son
//Police, Son2
//Police, Daughter
//Police, Daughter2
//Father
//Father, Mother
//Father, Son
//Father, Son2
//Mother
//Mother, Daughter
//Mother, Daughter2

If you enumerate Arranger instant directly, you will get enumeration of all possible combinations. But if you enumerate from SelectResults, you will get enumeration of the local variable of the possible combinations.

Now in step 2, we have to find combination of crossing.

var solutions = crossing.SelectResults(c => c.Value).Arrange(

    //Seed - list of people on target
    new Cross[] { 0 },

    //Func - add/subtract crossing people to/from target
    (list, item, i) => list.Append(list.Last() ^ item),

    //Yield - all people on target
    list => list.Last() == allPeople
);

In custom construction of Arranger class, arg1 (local variable) is the list of people on target land of each crossing. Arg2 (assignment) is to switch people on target land with the people who is crossing. Arg3 (solution) is people on target land must include all people.

Next is to append the break case.

//Thief cannot be with others without police
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Thief | Cross.Police)) == Cross.Thief) &&
    (list.Last() != Cross.Thief)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Thief | Cross.Police)) == Cross.Police) &&
    (opp(list.Last()) != Cross.Thief)
);

//Son cannot be with mother without father
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Mother) &&
    ((list.Last() & (Cross.Son | Cross.Son2)) > 0)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Father) &&
    ((opp(list.Last()) & (Cross.Son | Cross.Son2)) > 0)
);

//Daughter cannot be with father without mother
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Father) &&
    ((list.Last() & (Cross.Daughter | Cross.Daughter2)) > 0)
);
solutions.AppendBreak(list =>
    ((list.Last() & (Cross.Father | Cross.Mother)) == Cross.Mother) &&
    ((opp(list.Last()) & (Cross.Daughter | Cross.Daughter2)) > 0)
);

We don't care who is crossing. But if the crossing makes conflict in constraints, we will stop searching. Above, we stop searching if thief be with any persons without police, father be with daughter without mother, and mother be with son without father.

Now add more constraints.

//Cannot cross back
solutions.AppendConstraint(list => list.Length % 2 == 0, list => item => !list.Any((x, i) => (i % 2 == 0) && (x == (list.Last() ^ item))));
solutions.AppendConstraint(list => list.Length % 2 == 1, list => item => !list.Any((x, i) => (i % 2 == 1) && (x == (list.Last() ^ item))));

//Must have people to cross
solutions.AppendConstraint(list => list.Length % 2 == 0, list => item => (list.Last() & item) == item);
solutions.AppendConstraint(list => list.Length % 2 == 1, list => item => (~list.Last() & item) == item);

We now add 2 constraints. First constraint is to prevent cycle crossing by checking if the crossing create duplicate combination of people on target land. Second constraint is to limit people who are crossing must be available on the side which the raft is on.

All constraints are assigned. Then we output the result.

solutions.SelectResults().First().ForEach(x => {
    Console.WriteLine(opp(x));
    Console.WriteLine(x);
    Console.WriteLine("=============================================================");
});
//Thief, Police, Father, Mother, Son, Son2, Daughter, Daughter2
//0
//=============================================================
//Father, Mother, Son, Son2, Daughter, Daughter2
//Thief, Police
//=============================================================
//Police, Father, Mother, Son, Son2, Daughter, Daughter2
//Thief
//=============================================================
//Father, Mother, Son2, Daughter, Daughter2
//Thief, Police, Son
//=============================================================
//Thief, Police, Father, Mother, Son2, Daughter, Daughter2
//Son
//=============================================================
//Thief, Police, Mother, Daughter, Daughter2
//Father, Son, Son2
//=============================================================
//Thief, Police, Father, Mother, Daughter, Daughter2
//Son, Son2
//=============================================================
//Thief, Police, Daughter, Daughter2
//Father, Mother, Son, Son2
//=============================================================
//Thief, Police, Mother, Daughter, Daughter2
//Father, Son, Son2
//=============================================================
//Mother, Daughter, Daughter2
//Thief, Police, Father, Son, Son2
//=============================================================
//Father, Mother, Daughter, Daughter2
//Thief, Police, Son, Son2
//=============================================================
//Daughter, Daughter2
//Thief, Police, Father, Mother, Son, Son2
//=============================================================
//Mother, Daughter, Daughter2
//Thief, Police, Father, Son, Son2
//=============================================================
//Daughter2
//Thief, Police, Father, Mother, Son, Son2, Daughter
//=============================================================
//Thief, Police, Daughter2
//Father, Mother, Son, Son2, Daughter
//=============================================================
//Thief
//Police, Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================
//Thief, Police
//Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================
//0
//Thief, Police, Father, Mother, Son, Son2, Daughter, Daughter2
//=============================================================

Next post, we will find more extension for delegate types.

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.

Constraint Programming Part IV - LINQ

LINQ is a set of operators to query enumerable data. To query even numbers from set of 1 to 10, you may write:

var even = from x in 1.To(10)
           where x % 2 == 0
           select x;
//even = {2, 4, 6, 8, 10}

With using of LINQ, you can also do constraint programming. You can use "from" operator to join next member. You can append constraint by using "where" operator. And you can declare new variables by using "let" operator.

As an example, if you want to solve SEND + MORE = MONEY. Each letter represents a digit and there is no duplicated number among the letters. To solve this question, you may write:

var solutions = from d in 0.To(9)
                from e in 0.To(9).Except(new[] { d })
                from y in 0.To(9).Except(new[] { d, e })
                where (d + e) % 10 == y

                from n in 0.To(9).Except(new[] { d, e, y })
                from r in 0.To(9).Except(new[] { d, e, y, n })
                let nd = n * 10 + d
                let re = r * 10 + e
                let ey = e * 10 + y
                where (nd + re) % 100 == ey

                from o in 0.To(9).Except(new[] { d, e, y, n, r })
                let end = e * 100 + nd
                let ore = o * 100 + re
                let ney = n * 100 + ey
                where (end + ore) % 1000 == ney

                from s in 1.To(9).Except(new[] { d, e, y, n, r, o })
                from m in 1.To(9).Except(new[] { d, e, y, n, r, o, s })
                where s * 1000 + end + m * 1000 + ore == m * 10000 + o * 1000 + ney
                select new { s, e, n, d, m, o, r, y };
solutions.ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code above solves from last digit to the first digit. To translate the code, first block is to process last digit. D, E, and Y is a number in 0 to 9. Except method makes all letters are not duplicated. And there is a contraint that, D + E last digit must be Y. Upto this point, all solutions that D + E, last digit is not Y, will be filtered out.

Second block is to process last 2 digits, N and R is a number in 0 to 9 with no duplication. And now 3 variables are declared ND, RE, and EY. ND represents 2 digit number N and D, and the same for RE and EY. And there is a constraint ND + RE, last 2 digits must be EY.

Third block, is the same as second block, but is to precess last 3 digit. O is a number in 0 to 9 with no duplication. END + ORE, last 3 digits must be NEY.

Fourth block is to find the solution. S and M is a number in 1 to 9, first digit cannot be 0. And SEND + MORE must be equal to MONEY. Then select the result.

Now compare LINQ code with using arranger class.

Func<int, int, int, int, int> mix = (a, b, c, d) => a * 1000 + b * 100 + c * 10 + d;
int D = 0, E = 1, Y = 2, N = 3, R = 4, O = 5, S = 6, M = 7;
var sol = 0.To(9).Arrange(8);
sol.ArrangementModel = ArrangementModel.Permutation;
sol.AppendConstraint(set => set.Length == Y, set => y => (set[D] + set[E]) % 10 == y);

sol.AppendConstraint(set => set.Length == R, set => r => (mix(0, 0, set[N], set[D]) + mix(0, 0, r, set[E])) % 100 == mix(0, 0, set[E], set[Y]));
sol.AppendConstraint(set => set.Length == O, set => o => (mix(0, set[E], set[N], set[D]) + mix(0, o, set[R], set[E])) % 1000 == mix(0, set[N], set[E], set[Y]));

sol.AppendConstraint(set => set.Length == S, set => s => s != 0);
sol.AppendConstraint(set => set.Length == M, set => m => m != 0);
sol.AppendConstraint(set => set.Length == M, set => m => mix(set[S], set[E], set[N], set[D]) + mix(m, set[O], set[R], set[E]) == m * 10000 + mix(set[O], set[N], set[E], set[Y]));

sol.SelectResults(set => new { s = set[S], e = set[E], n = set[N], d = set[D], m = set[M], o = set[O], r = set[R], y = set[Y] })
    .ForEach(Console.WriteLine);
//{ s = 9, e = 5, n = 6, d = 7, m = 1, o = 0, r = 8, y = 2 }

The code is much more confusing. To translate code above, mix function is function to join digits together. Arragement model is permutation, because each letter cannot be duplicated. First constraint, processed when get Y, D + E, last digit is Y.

Second constraint, processed when get R, ND + RE, last 2 digits must be EY. Third constraint, processed when get O, END + ORE, last 3 digits must be NEY.

Fouth and fifth constraint, processed when get S and M, S and M must not equal to 0. Last constraint, processed when get the last member M. SEND + MORE must be equal to MONEY.

To solve a constraint satisfaction problem, sometimes, when each constraint is applied to only one member, solving the problem using LINQ is better. But if constraints are applied to all members like 8 queens or sudoku, using Arranger class is better.

Next, we will solve problem with using LINQ and arranger in combination. The problem is Einstein's puzzle.