This is the thirty second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hello! Today we will solve classic constraint programming riddle using ILP.

Rules

Farmer has wolf, goat, and cabbage. He wants to cross the river with all his stuff, but he has small boat and is able to move to the other bank of the river with only one thing in it. What’s more, if wolf stays alone (without farmer) with the goat, he eats it. If goat stays alone (without farmer) with the cabbage, she eats it. We want to find minimum number of moves allowing to cross the river.

Implementation

Unfortunately, there is probably no magic solution here, we just need to examine all possible states. Of course we are not going to implement this by hand, we want ILP solver to solve it for us.

We represent position of every player (farmer, wolf, cabbage, goat) as a binary integer. False indicates that player is on the left side of the river (initial position), true indicates that player is on the right side.

In every turn we modify variables: since we don’t know the minimum number of moves, we need to estimate its upper bound. Since there is $2^4$ possible states, we assume that there will be no more than $16$ turns. If that doesn’t hold it means that some state is repeated, which for sure will not happen in optimal solution.

In every turn we are allowed to move at most two players. What’s more, only farmer is able to drive the boat, so he must move if anyone does. We also need to prohibit some states: in order to do that, we will easily hash current state by multiplying players’ variables by powers of two, so our state will be unambiguous.

Since writing down all variables would be cumbersome, we will get down to C# code. We will use looping here, so our transformations will be pretty easy.

using System;
using System.Collections.Generic;
using System.Linq;
using MilpManager.Abstraction;
using MilpManager.Implementation;
using MilpManager.Implementation.CompositeOperations;
using OrToolsMilpManager.Implementation;

namespace WolfGoatCabbage
{
    class Program
    {
        static void Main()
        {
            var solver = new OrToolsMilpSolver(5);

            // Weights, they need to be separate in order to hash state easily
            int farmerWeight = 1<<3;
            int wolfWeight = 1<<2;
            int cabbageWeight = 1<<1;
            int goatWeight = 1<<0;

            // In order to track changes
            var farmerVariables = new List< IVariable>();
            var wolfVariables = new List< IVariable>();
            var cabbageVariables = new List< IVariable>();
            var goatVariables = new List< IVariable>();

            // State in the previous turn
            IVariable oldSide = null;

            // At start farmer is on the left side
            int farmerSide = 0;

            var result = solver.CompositeOperation(CompositeOperationType.Loop, new LoopParameters
            {
                // We have at most 2^4 states
                MaxIterations = 2*2*2*2,
                Body = new Func< IVariable, IVariable[], IVariable>[]
                {
                    (counter, all) =>
                    {
                        // We hash current state
                        IVariable newSum = solver.Operation(OperationType.Addition, all[0].Operation(OperationType.Multiplication, solver.FromConstant(farmerWeight)),
                            all[1].Operation(OperationType.Multiplication, solver.FromConstant(wolfWeight)),
                            all[2].Operation(OperationType.Multiplication, solver.FromConstant(cabbageWeight)),
                            all[3].Operation(OperationType.Multiplication, solver.FromConstant(goatWeight)));
                        // We sum variables in order to know how many palyers are on the right side
                        IVariable newSide = solver.Operation(OperationType.Addition, all);

                        // If this is another iteration
                        if (oldSide != null)
                        {
                            // Disable states
                            newSum.Set(CompositeConstraintType.NotFromSet, null,
                                // Cabbage and goat alone on the right side
                                solver.FromConstant(cabbageWeight + goatWeight),
                                // Wolf and goat alone on the right side
                                solver.FromConstant(wolfWeight + goatWeight),
                                // Farmer on the left side, all the others on the right side
                                solver.FromConstant(wolfWeight + cabbageWeight + goatWeight),
                                // Farmer on the right side, all the others on the left side
                                solver.FromConstant(farmerWeight),
                                // Wolf and goat alone on the left side
                                solver.FromConstant(farmerWeight + cabbageWeight),
                                // Goad and cabbage alone on the left side
                                solver.FromConstant(farmerWeight + wolfWeight)
                            );

                            // Who moved right
                            var onlyRightMoves = solver.Operation(OperationType.Conjunction, 
                                all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
                                all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
                                all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),
                                all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0))
                            );

                            // Who moved left
                            var onlyLeftMoves = solver.Operation(OperationType.Conjunction,
                                all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
                                all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
                                all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),
                                all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0))
                            );

                            // At most two players can move in this turn
                            // We know that if someone moves, it is farmer with someone else
                            newSide.Operation(OperationType.Subtraction, oldSide).Operation(OperationType.AbsoluteValue).Set(ConstraintType.LessOrEqual, solver.FromConstant(2));

                            // We allow only coherent moves (all from left to right or all from right to left)
                            onlyRightMoves.Operation(OperationType.Disjunction, onlyLeftMoves).MakeTrue();
                        }

                        // Farmer changes side
                        farmerSide = 1 - farmerSide;
                        var newFarmer = all[0].Operation(OperationType.BinaryNegation);
                        farmerSide = 1 - farmerSide;

                        // Store existing state
                        oldSide = newSide;
                        farmerVariables.Add(all[0]);
                        wolfVariables.Add(all[1]);
                        cabbageVariables.Add(all[2]);
                        goatVariables.Add(all[3]);

                        // Return new variable
                        return newFarmer;
                    },
                    (counter, all) => solver.CreateAnonymous(Domain.BinaryInteger),
                    (counter, all) => solver.CreateAnonymous(Domain.BinaryInteger),
                    (counter, all) => solver.CreateAnonymous(Domain.BinaryInteger)
                }
            }, 
            solver.FromConstant(0), // farmer on the left side
            solver.FromConstant(0), // wolf on the left side
            solver.FromConstant(0), // cabbage on the left side
            solver.FromConstant(0) // goat on the left side
            ).ToArray();
            var moves = result.Reverse().First();

            oldSide.Set(ConstraintType.Equal, solver.FromConstant(4)); // everyone on the right side

            solver.AddGoal("minimizeMoves", moves.MakeGoal(GoalType.Minimize));
            solver.Solve();

            for (int i = 0; i <= (int)moves.GetValue(); ++i)
            {
                Console.WriteLine(
                    $"Iteration: {i}\nFarmer: {Side(farmerVariables[i].GetValue())}, Wolf: {Side(wolfVariables[i].GetValue())}, Cabbage: {Side(cabbageVariables[i].GetValue())}, Goat: {Side(goatVariables[i].GetValue())}");
            }
        }

        private static string Side(double value)
        {
            return (int)Math.Round(value) == 0 ? "Left" : "Right";
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

using System;

using System.Collections.Generic;

using System.Linq;

using MilpManager.Abstraction;

using MilpManager.Implementation;

using MilpManager.Implementation.CompositeOperations;

using OrToolsMilpManager.Implementation;

namespace WolfGoatCabbage

{

class Program

{

static void Main()

{

var solver = new OrToolsMilpSolver(5);

// Weights, they need to be separate in order to hash state easily

int farmerWeight = 1<<3;

int wolfWeight = 1<<2;

int cabbageWeight = 1<<1;

int goatWeight = 1<<0;

// In order to track changes

var farmerVariables = new List< IVariable>();

var wolfVariables = new List< IVariable>();

var cabbageVariables = new List< IVariable>();

var goatVariables = new List< IVariable>();

// State in the previous turn

IVariable oldSide = null;

// At start farmer is on the left side

int farmerSide = 0;

var result = solver.CompositeOperation(CompositeOperationType.Loop, new LoopParameters

{

// We have at most 2^4 states

MaxIterations = 2*2*2*2,

Body = new Func< IVariable, IVariable[], IVariable>[]

{

(counter, all) =>

{

// We hash current state

IVariable newSum = solver.Operation(OperationType.Addition, all[0].Operation(OperationType.Multiplication, solver.FromConstant(farmerWeight)),

all[1].Operation(OperationType.Multiplication, solver.FromConstant(wolfWeight)),

all[2].Operation(OperationType.Multiplication, solver.FromConstant(cabbageWeight)),

all[3].Operation(OperationType.Multiplication, solver.FromConstant(goatWeight)));

// We sum variables in order to know how many palyers are on the right side

IVariable newSide = solver.Operation(OperationType.Addition, all);

// If this is another iteration

if (oldSide != null)

{

// Disable states

newSum.Set(CompositeConstraintType.NotFromSet, null,

// Cabbage and goat alone on the right side

solver.FromConstant(cabbageWeight + goatWeight),

// Wolf and goat alone on the right side

solver.FromConstant(wolfWeight + goatWeight),

// Farmer on the left side, all the others on the right side

solver.FromConstant(wolfWeight + cabbageWeight + goatWeight),

// Farmer on the right side, all the others on the left side

solver.FromConstant(farmerWeight),

// Wolf and goat alone on the left side

solver.FromConstant(farmerWeight + cabbageWeight),

// Goad and cabbage alone on the left side

solver.FromConstant(farmerWeight + wolfWeight)

);

// Who moved right

var onlyRightMoves = solver.Operation(OperationType.Conjunction,

all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),

all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),

all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0)),

all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsGreaterOrEqual, solver.FromConstant(0))

);

// Who moved left

var onlyLeftMoves = solver.Operation(OperationType.Conjunction,

all[0].Operation(OperationType.Subtraction, farmerVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),

all[1].Operation(OperationType.Subtraction, wolfVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),

all[2].Operation(OperationType.Subtraction, cabbageVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0)),

all[3].Operation(OperationType.Subtraction, goatVariables.Last()).Operation(OperationType.IsLessOrEqual, solver.FromConstant(0))

);

// At most two players can move in this turn

// We know that if someone moves, it is farmer with someone else

newSide.Operation(OperationType.Subtraction, oldSide).Operation(OperationType.AbsoluteValue).Set(ConstraintType.LessOrEqual, solver.FromConstant(2));

// We allow only coherent moves (all from left to right or all from right to left)

onlyRightMoves.Operation(OperationType.Disjunction, onlyLeftMoves).MakeTrue();

}

// Farmer changes side

farmerSide = 1 - farmerSide;

var newFarmer = all[0].Operation(OperationType.BinaryNegation);

farmerSide = 1 - farmerSide;

// Store existing state

oldSide = newSide;

farmerVariables.Add(all[0]);

wolfVariables.Add(all[1]);

cabbageVariables.Add(all[2]);

goatVariables.Add(all[3]);

// Return new variable

return newFarmer;

(counter, all) => solver.CreateAnonymous(Domain.BinaryInteger),

(counter, all) => solver.CreateAnonymous(Domain.BinaryInteger)

}

solver.FromConstant(0), // farmer on the left side

solver.FromConstant(0), // wolf on the left side

solver.FromConstant(0), // cabbage on the left side

solver.FromConstant(0) // goat on the left side

).ToArray();

var moves = result.Reverse().First();

oldSide.Set(ConstraintType.Equal, solver.FromConstant(4)); // everyone on the right side

solver.AddGoal("minimizeMoves", moves.MakeGoal(GoalType.Minimize));

solver.Solve();

for (int i = 0; i <= (int)moves.GetValue(); ++i)

{

Console.WriteLine(

$"Iteration: {i}\nFarmer: {Side(farmerVariables[i].GetValue())}, Wolf: {Side(wolfVariables[i].GetValue())}, Cabbage: {Side(cabbageVariables[i].GetValue())}, Goat: {Side(goatVariables[i].GetValue())}");

}

private static string Side(double value)

{

return (int)Math.Round(value) == 0 ? "Left" : "Right";

}

Output:

Iteration: 0
Farmer: Left, Wolf: Left, Cabbage: Left, Goat: Left
Iteration: 1
Farmer: Right, Wolf: Left, Cabbage: Left, Goat: Right
Iteration: 2
Farmer: Left, Wolf: Left, Cabbage: Left, Goat: Right
Iteration: 3
Farmer: Right, Wolf: Left, Cabbage: Right, Goat: Right
Iteration: 4
Farmer: Left, Wolf: Left, Cabbage: Right, Goat: Left
Iteration: 5
Farmer: Right, Wolf: Right, Cabbage: Right, Goat: Left
Iteration: 6
Farmer: Left, Wolf: Right, Cabbage: Right, Goat: Left
Iteration: 7
Farmer: Right, Wolf: Right, Cabbage: Right, Goat: Right

Iteration: 0

Farmer: Left, Wolf: Left, Cabbage: Left, Goat: Left

Iteration: 1

Farmer: Right, Wolf: Left, Cabbage: Left, Goat: Right

Iteration: 2

Farmer: Left, Wolf: Left, Cabbage: Left, Goat: Right

Iteration: 3

Farmer: Right, Wolf: Left, Cabbage: Right, Goat: Right

Iteration: 4

Farmer: Left, Wolf: Left, Cabbage: Right, Goat: Left

Iteration: 5

Farmer: Right, Wolf: Right, Cabbage: Right, Goat: Left

Iteration: 6

Farmer: Left, Wolf: Right, Cabbage: Right, Goat: Left

Iteration: 7

Farmer: Right, Wolf: Right, Cabbage: Right, Goat: Right

Summary

It looks like implementing this riddle is not that hard.