ILP Part 32 — Wolf, goat, cabbage, and farmer

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.

Output:

Summary

It looks like implementing this riddle is not that hard.