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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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), (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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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.