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 possible states, we assume that there will be no more than 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

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

// 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.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
```

# Summary

It looks like implementing this riddle is not that hard.