Solving River Crossing Puzzles With MiniZinc

The objective of river crossing puzzles is to bring items from one river bank to the other in the fewest possible steps. One prominent puzzle is the wolf, goat and cabbage problem. From Wikipedia:

“Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage.

The farmer’s challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?”

MiniZinc

MiniZinc is a high-level constraint modeling language. It allows you to model optimization and constraint satisfaction problems. In the backend, one is free to choose from a wide range of solvers.

Structure of MiniZinc Models

A MiniZinc model consists of parameters, decision variables, constraints, objective, and output. They all can be specified in any order.

Parameters

Parameters define the concrete inputs for the model. In our river crossing puzzle, the parameters can be defined as follows:

enum PASSENGER = {Farmer, Wolf, Goat, Cabbage};
enum LOC = {bankA, bankB};

int: maxstep = 10;
set of int: STEP0 = 0..maxstep;
set of int: STEP = 1..maxstep;

Apart from the enumerations, the only parameter in this puzzle is maxstep. It is always a good idea to specify some upper bound for the search space during modeling. STEP0 and STEP1 are two index sets. We will need these later.

Decision Variables

A decision variable represents the unknown solution space. In our puzzle, we are looking for the farmer’s concrete steps to carry the purchases to the far bank of the river. In MiniZinc, we can use arrays or var variables to represent the unknown locations at each step:

array[STEP0] of var LOC: farmerLoc;
array[STEP0] of var LOC: wolfLoc;
array[STEP0] of var LOC: goatLoc;
array[STEP0] of var LOC: cabbageLoc;

% Helper type: two-dimensional array of the unknown locations.
array[PASSENGER, STEP0] of var LOC: loc =
    array2d(PASSENGER, STEP0,
            farmerLoc ++ wolfLoc ++ goatLoc ++ cabbageLoc);

var STEP: end;

The end variable represents the unknown number of steps to solve the puzzle.

Constraints

The constraints define the restrictions on the decision variables:

“the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage.”

Modeling constraints is the most challenging (and fun) part of MiniZinc. Fortunately, you can use established techniques for modeling common problems. In the following, we will constrain the farmer’s locations and his purchases at each step to represent the boat crossing the river.

% The farmer arrives at the river with his purchases.
constraint forall(p in PASSENGER)(loc[p,0] = bankA);
% The farmer crosses the river with his purchases after end steps.
constraint forall(p in PASSENGER, s in STEP where s >= end)
                 (loc[p,s] = bankB);
constraint end <= maxstep;

How should we model the crossing of the river? We can simply iterate over the loc array and constrain the previous and the next location of the farmer and his items. To avoid code duplication, we can create a predicate.

% If the location of a passenger changes from one river bank
% to the other, so should change the location of the farmer too.
% Note that STEP is 1..maxtep allowing us to access s-1.
predicate passenger_moves(var PASSENGER: p, var STEP: s) =
    let { var LOC: farmer_last_pos = loc[Farmer,s-1];
          var LOC: farmer_new_pos = loc[Farmer,s];
          var LOC: last_pos = loc[p,s-1];
          var LOC: new_pos = loc[p,s]; } in
          last_pos != new_pos
          ->
          farmer_last_pos = last_pos /\ farmer_new_pos = new_pos;
% Constrain all passengers (farmer and his purchases).
constraint forall(p in PASSENGER, s in STEP)(passenger_moves(p, s));

Done! Let’s finish by adding the two remaining constraints.

% Never leave the wolf with the goat or the goat with the cabbage alone.
constraint forall(s in STEP)
                 (wolfLoc[s] = goatLoc[s] \/ goatLoc[s] = cabbageLoc[s] 
                  ->
                  farmerLoc[s] = goatLoc[s]);

% The farmer can carry only himself and a single one of his purchases.
% If the location of the farmer changes, at most one purchase can
% change its location as well.
constraint forall(s in STEP)
                 (farmerLoc[s-1] != farmerLoc[s]
                  ->
                  sum(p in PASSENGER where p != Farmer)
                     (loc[p,s-1] != loc[p,s])
                  <= 1);

Objective

The objective function can be either constraint satisfaction or minimization/maximization of the decision variables. We are looking for the least number of steps to cross the river.

solve minimize end;

Output

Printing custom output of the solution is optional and a bit tricky. There are built-in MiniZinc functions for that, and together with the support of emojis, we can craft the explanation of the solution found by MiniZinc.

% Our emojis.
array[PASSENGER] of string: emoji = ["👨‍🌾","🐺","🐐","🥬"] ::output_only;

output
[ "Step \(s): " ++ % step prefix
  show([ emoji[p] | p in PASSENGER where fix(loc[p,s]) = bankA ]) ++
  " <-> " ++
  show([ emoji[p] | p in PASSENGER where fix(loc[p,s]) = bankB ]) ++
  "\n"
  | s in 1..fix(end) ]; % generator

It’s time to put the pieces together and run our model. Assuming you have MiniZinc available in your PATH, pass the model file to the executable.

$ minizinc --version
MiniZinc to FlatZinc converter, version 2.5.3, build 220798393
Copyright (C) 2014-2020 Monash University, NICTA, Data61

$ time minizinc farmer-wolf-goat-cabbage.mzn
Step 1: ["🐺", "🥬"] <-> ["🧑🏻‍🌾", "🐐"]
Step 2: ["🧑🏻‍🌾", "🐺", "🥬"] <-> ["🐐"]
Step 3: ["🥬"] <-> ["🧑🏻‍🌾", "🐺", "🐐"]
Step 4: ["🧑🏻‍🌾", "🐐", "🥬"] <-> ["🐺"]
Step 5: ["🐐"] <-> ["🧑🏻‍🌾", "🐺", "🥬"]
Step 6: ["🧑🏻‍🌾", "🐐"] <-> ["🐺", "🥬"]
Step 7: [] <-> ["🧑🏻‍🌾", "🐺", "🐐", "🥬"]
----------
==========

real	0m0.850s
user	0m0.072s
sys	0m0.059s

We need 7 steps to cross the river, and this is provably the minimal solution! Grab the model from GitHub and try it yourself.

Conclusion

This post was inspired by the MiniZinc tutorial of Lucas DiCioccio. There are many ways to model this problem. I used the techniques from the two MiniZinc courses available in Coursera, Basic Modeling for Discrete Optimization and Advanced Modeling for Discrete Optimization, which I highly recommend.

Subscribe via RSS or follow @rsasnauskas on Twitter for more.