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.