Wolf, Goat and Cabbage

What is this repository for?

This code uses a mixed integer programming (MIP) model to solve a logic puzzle posted in which a farmer, for unspecified reasons, buys a wolf, a goat and a cabbage. On the way home, the farmer encounters a river that must be crossed by boat. The boat has only enough room for the farmer and one purchase at a time. If the wolf and goat are left alone together, the wolf will eat the goat. Similarly, if the goat and cabbage are left alone together, the goat will eat the cabbage. (The wolf and the cabbage apparently get along amicably.) The puzzle is to find a sequence of trips across the river that result in the farmer and all three purchases ending up intact on the far side of the river.

The MIP model solves the puzzle with the objective of minimizing the number of river crossings required to achieve the desired terminal state.

Details

The code was developed using a beta version of CPLEX 22.1 but will run with any version. CPLEX is overkill for a problem this size. Any MIP solver would do.

The model formulation is discussed in my blog post.

License

The code here is copyrighted by Paul A. Rubin (yours truly) and licensed under a Creative Commons Attribution 3.0 Unported License.