The Wolf, the Goat, and the Cabbage

… in which we revisit miniKanren and use it to solve a planning puzzle about ferrying some items safely across a river.

miniKanren is a logic programing language embedded inside Racket, a "Domain Specific Language" or a DSL. There are lots of learning resources for miniKanren listed on its website, but perhaps the most popular introduction to the language is The Reasoned Schemer book.

In a previous blog post, I explored using miniKanren to solve a constraint problem, where a solution has to be found based on some stated constraints, in this blog post we’ll look at solving a planning problem, where a plan, which is a list of steps, has to be constructed to arrive at a desired state.

The Puzzle

The puzzle that we’ll solve is called The Wolf, the Goat and The Cabbage puzzle and it goes like this:

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.

It might be useful to attempt to solve the puzzle using pencil and paper first, it is not too complicated and the solution is provided in the link above. In particular, there is one special insight that is required for miniKanren to be able to solve this problem.

And here is a unrelated picture of a goat:

The Language

The miniKanren implementation is quite small and the authors of "The Reasoned Schemer" explain its inner workings in one short chapter. There are many implementations you can use, available on the miniKanren website, but the examples below are written using the language defined in the Second Edition of The Reasoned Schemer, which has some differences from the first edition.

You can find the official second edition implementation here, but for this blog post I wrote my own miniKanren implementation, which I used for solving the puzzle. Since this is my implementation, I took the liberty of renaming some operators, as I believe it makes them more readable, in particular, the book uses conde, here I use cond/e, the book uses membero, here I use member/o.

You can find my version of miniKanren in this GitHub Gist, to start using it, simply copy the racket file in a local folder and start the programs with the lines below. Since we’ll write some unit tests as well, we’ll set up the test environment by preparing the test module:

1
2

#lang racket
(require "mk.rkt")

If you are completely new to miniKanren, I suggest to get and read the book, or at least having a look at the previous blog post first.

The Solution

We’ll build the solution from the ground up, starting with basic miniKanren relations and working towards the more complex ones — I must confess that this is not how I actually solved the problem, but it does make it easier to explain. In addition to that, at every step, all introduced relations work and can be tested in a Racket REPL.

Introducing the Participants

We’ll start by writing the relation participant/o, which determines if a term is a participant in our puzzle. The participants are the “Wolf”, the “Goat” and the “Cabbage”, and the relation simply uses member/o to determine if the term x is in the list of valid participants:

1
2

(defrel (participant/o x)
  (member/o x '(Goat Wolf Cabbage)))

It is important to understand that participant/o is not just a function with inputs and outputs. Sure, it can check if a value is a participant or not:

1
2
3
4
5
6

;; The 'Goat is a participant
> (run 1 q (fresh () (participant/o 'Goat) (== q 'Success)))
'(Success)
;; The 'Rabbit is not a particiant, and run produces no results
> (run 1 q (fresh () (participant/o 'Rabbit) (== q 'Success)))
'()

… but the relation can also be used to determine who are the participants themselves:

1
2

> (run* q (participant/o q))
'(Goat Wolf Cabbage)

The puzzle participants are not friends: they eat each other. This is encoded in the eats/o relation which defines who-eats-who. Being a relation, it can also answer the opposite question, “Who is eaten by whom?”, as well as to enumereate all the who-eats-who relationships.

1
2
3
4

(defrel (eats/o who what)
  (cond/e
    ((== who 'Goat) (== what 'Cabbage))
    ((== who 'Wolf) (== what 'Goat))))

Here is how the relation works:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

;; What does the Goat eat?  What does the Wolf eat?
> (run 1 q (eats/o 'Goat q))
'(Cabbage)
> (run 1 q (eats/o 'Wolf q))
'(Goat)

;; Who eats the Cabbage? Who eats the Goat?, Who eats the Wolf? (no one)
> (run 1 q (eats/o q 'Cabbage))
'(Goat)
> (run 1 q (eats/o q 'Goat))
'(Wolf)
> (run 1 q (eats/o q 'Wolf))
'()

Participant Groups

We’ll represent a group of participants on the river bank using a list, for example, the list (Wolf Cabbage) means that the Wolf and Cabbage are on a river bank and the empty list ’() means there are no participants on a river bank.

Since there is one participant of each type in the puzzle, we need to enforce this restriction. For example, (Wolf Cabbage) is a group, but (Wolf Cabbage Wolf) is not, since there is only one Wolf in our puzzle.

We’ll implement a helper relation, group-helper/o which checks if g is a valid group, that is, a list of unique participants. It does that by checking that each item in the list is valid and tracking which participants have been seen so far. The group/o relation enforces that g is a valid group, or generates all valid groups. It simply starts group-helper/o with an empty “seen” list

Note the use of cond/a in the check below — the cond/a differs form cond/e in that the first branch that succeedes will produce values and this is important if we want to fail for seen participants.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

(defrel (group-helper/o g seen)
  (cond/e
    ((== g '()))                        ; The empty group is a valid group.
    ((fresh (head tail)
       ;; Otherwise the group is a list with a HEAD and a TAIL
       (cons/o head tail g)
       ;; The first element of the group (HEAD) needs to be a valid
       ;; participant
       (participant/o head)
       (cond/a
         ;; If we have seen this participant before, we fail
         ((once (member/o head seen)) fail)
         ((fresh (updated)
            ;; otherwise add this participant to the seen ones and check the
            ;; remaining of the list.
            (cons/o head seen updated)
            (group-helper/o tail updated))))))))
            
(defrel (group/o g)
  (group-helper/o g '()))

Let’s see how this works:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

;; The empty group is a valid group
> (run 1 q (fresh () (group/o '()) (== q 'Success)))
'(Success)
;; ... and so are '(Wolf Cabbage) '(Cabbage Wolf)
> (run 1 q (fresh () (group/o '(Wolf Cabbage)) (== q 'Success)))
'(Success)
> (run 1 q (fresh () (group/o '(Cabbage Wolf)) (== q 'Success)))
'(Success)
;; ... but duplicates are not valid groups
(run 1 q (fresh () (group/o '(Wolf Cabbage Wolf)) (== q 'Success)))
'()

The group/o relation can also be used to generate all the valid groups in the puzzle, and there is only 16 of them:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

;; List all groups
> (run* q (group/o q))
'(()
 (Goat)
 (Wolf)
 (Cabbage)
 (Goat Wolf)
 (Goat Cabbage)
 (Wolf Goat)
 (Cabbage Goat)
 (Goat Wolf Cabbage)
 (Wolf Cabbage)
 (Goat Cabbage Wolf)
 (Cabbage Wolf)
 (Wolf Goat Cabbage)
 (Cabbage Goat Wolf)
 (Wolf Cabbage Goat)
 (Cabbage Wolf Goat))

Some participant groups are safe to be left unattended, some are not. (Wolf Cabbage) is safe, since the Wolf does not eat Cabbage, but (Goat Cabbage) is not, since the Goat, left unsupervised, will eat the Cabbage. The safe-group/o relation checks if a group g is safe, it does that by checking that no two members of a group can eat each other:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(defrel (safe-group/o g)
  ;; `g` must be a valid group
  (group/o g)
  ;; The use of `cond/u` here, instead of `cond/a` is an optimisation -- when
  ;; we fail beacuse found one set of who/what eats in the group , we don't
  ;; need to try any other combinations of who/what anymore.
  (cond/u ((fresh (who what)
             (eats/o who what)
             (member/o who g)
             (member/o what g))
           ;; fail if we find a pair of participants who eat each other...
           fail)
          (succeed)))

Let’s try it out:

1
2
3
4
5
6
7
8
9

;; The empty group is safe
> (run 1 q (fresh () (safe-group/o '()) (== q 'Success)))
'(Success)
;; The Wolf does not eat the Cabbage, so `(Wolf Cabbage) is safe
> (run 1 q (fresh () (safe-group/o '(Wolf Cabbage)) (== q 'Success)))
'(Success)
;; ... but the Goat does eat the Cabbage, so `(Goat Cabbage) is not safe
< (run 1 q (fresh () (safe-group/o '(Goat Cabbage)) (== q 'Success))
'()

As with group/o, the safe-group/o relation can also be used to generate all the safe groups in the puzzle, and there is only 6 of them:

1
2
3
4
5
6
7

> (run* q (safe-group/o q))
'(()
  (Goat)
  (Wolf)
  (Cabbage)
  (Wolf Cabbage)
  (Cabbage Wolf))

Candidate Picking

The puzzle requires us to pick a participant form a group and ferry them across the river. This has to be done in such a way that the participants that remain on the river bank won’t eat each other. The pick/o relation allows picking a participant from a group, g, such that the remaining participants form a safe group. The normal use case is that g is an “input” to the relation, and the participant and the remaining group are “output” to the participant and out parameters, however this is just one use case, the relation can also be used to determine what group g can be formed by “unpicking” a participant from an output group (we’ll see examples of this below):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

(defrel (pick/o g participant out)
  (group/o g)
  (fresh (head tail)
    (cons/o head tail g)
    (cond/e
      ((== participant head)
       (== out tail))
      ((fresh (intermediate)
         (pick/o tail participant intermediate)
         (cons/o head intermediate out)))))
  (safe-group/o out))

Let’s see how this relation works in the normal use case:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

;; There is nothing to pick from an empty group
> (run 1 q (fresh (c o) (pick/o '() c o) (== q 'Success)))
'()
;; If there is only one participant, there is only one pick
> (run* (participant remaining) (pick/o '(Goat) participant remaining))
'((Goat ()))
;; If there are two possibilities, they can both be picked
> (run* (participant remaining) (pick/o '(Goat Wolf) participant remaining))
'((Goat (Wolf))
  (Wolf (Goat)))
;; However, from the `(Goat Wolf Cabbage) group only Goat can be picked so
;; the remaining participants don't eat each other.
> (run* (participant remaining) (pick/o '(Goat Cabbage Wolf) participant remaining))
'((Goat (Cabbage Wolf)))

The pick/o relation can also be used to find all the groups from which Cabbage can be picked. Note that the group (Goat Cabbage Wolf) is not in this list, since we cannot pick Cabbage from that group and still leaving the group safe (the Wolf will eat the Goat):

1
2
3
4
5
6

> (run* q (fresh (o) (pick/o q 'Cabbage o)))
'((Cabbage)
  (Goat Cabbage)
  (Cabbage Goat)
  (Wolf Cabbage)
  (Cabbage Wolf))

While the pick/o relation will pick an existing participant from a group, this is not sufficient to be to solve the puzzle. An insight to solving the puzzle is to realize that the boat can ferry empty across the river, that is, if the group on a river bank is safe, where no one gets eaten (e.g. Wolf and Cabbage), than we have the option of ferrying Nothing to the other bank, in addition to picking one of the participant from the group:

1
2
3
4
5
6
7

(defrel (pick-maybe-nothing/o g participant out)
  (cond/e
    ((safe-group/o g)
     ;; If the group is safe, there is an option to pick 'Nothing
     (== participant 'Nothing)
     (== out g))
    ((pick/o g participant out))))

The pick-maybe-nothing/o allows us to pick “nothing” from an empty group, or from safe groups to pick either one of the participants or nothing:

1
2
3
4

> (run 1 q (fresh (o) (pick-maybe-nothing/o '() q o)))
'(Nothing)
> (run* q (fresh (o) (pick-maybe-nothing/o '(Goat) q o)))
'(Nothing Goat)

The pick-maybe-nothing/o relation can also be used to find from which groups we can pick ’Nothing, these are effectively all the safe groups, as defined by the safe-group/o relation:

1
2
3
4
5
6
7

> (run* q (fresh (o) (pick-maybe-nothing/o q 'Nothing o)))
'(()
  (Goat)
  (Wolf)
  (Cabbage)
  (Wolf Cabbage)
  (Cabbage Wolf))

Same Group

The pick/o relation can be used “in reverse” to determine from what groups we can pick a Cabbage and remain with a Wolf:

1
2

> (run* q (pick/o q 'Cabbage '(Wolf)))
'((Wolf Cabbage) (Cabbage Wolf))

Since we don’t constrain the order of participants in groups, (Wolf Cabbage) and (Cabbage Wolf) are considered different groups by the group/o relation, and this can create problems when searching for a solution: since we want to avoid getting into the same state again (such as by just ferrying the Goat back and forth across the river), we need a relation to determine if two participant groups are the same, that is, they contain the same participants, regardless of the order in which they appear.

We’ll define the same/o relation in terms of two other relations, one that succeeds when two lists l1 and l2 have the same number of elements, and a second one which succeeds when each element from l1 is present in l2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

(defrel (same/o l1 l2)
  (same-length/o l1 l2) ; same number of elements in l1 and l2
  (subset-of/o l1 l2)   ; all elements in l1 are in l2
  (subset-of/o l2 l1))  ; all elements in l2 are in l1

;; Succeed if l1 and l2 have the same number of elements
(defrel (same-length/o l1 l2)
  (cond/e
    ((null/o l1) (null/o l2))
    ((fresh (a1 d1 a2 d2)
       (cons/o a1 d1 l1)
       (cons/o a2 d2 l2)
       (same-length/o d1 d2)))))
;; Succeed if every element from l1 is present in l2
(defrel (subset-of/o l1 l2)
  (cond/e
    ((null/o l1))
    ((fresh (a d)
       (cons/o a d l1)
       (proper-member/o a l2)
       (subset-of/o d l2)))))

Below are some basic usage of the same/o relation: it succeeds and fails as expected.

1
2
3
4

> (run 1 q (fresh () (same/o '(Wolf Cabbage) '(Cabbage Wolf)) (== q 'Succeed)))
'(Succeed)
> (run 1 q (fresh () (same/o '(Wolf Cabbage) '(Wolf Cabbage Goat)) (== q 'Succeed)))
'()

The same/o relation can also be used to generate all permutations of list elements: we can generate all the lists which would be the same as one of the input lists:

1
2
3
4
5
6
7

> (run* q (same/o '(Wolf Goat Cabbage) q))
'((Wolf Goat Cabbage)
  (Wolf Cabbage Goat)
  (Goat Wolf Cabbage)
  (Goat Cabbage Wolf)
  (Cabbage Wolf Goat)
  (Cabbage Goat Wolf))

Search History

As we search for a river crossing solution, we’ll need to keep track of the groups we have seen, to avoid going in an infinite loop: ferrying the Goat accross the river back and forth will satisfy the condition that the participants left on either river bank are in a safe group, but it keep trying forever and will never find a solution to the puzzle.

While planning the solution, we’ll keep track of the previous groups we have seen seen and check if the newly proposed group is in fact a new one. seen-group/o will check if a group g is present in history which is a list of groups:

1
2
3
4
5

(defrel (seen-group/o g history)
  (fresh (head tail)
    (cons/o head tail history)
    (cond/e ((same/o g head))
            ((seen-group/o g tail)))))

The implementation seen-group/o is similar to the member/o relation, except we use same/o to check if the items are the same, since a group of participants is the same regardless of the order in which they appear:

1
2
3
4
5
6

;; History is empty, so the '(Goat) group was not seen
> (run 1 q (fresh () (seen-group/o '(Goat) '())) (== q 'Succeed))
'()
;; The '(Wolf Cabbage) group is "seen" even though it appears in a different order
> (run 1 q (fresh () (seen-group/o '(Wolf Cabbage) '((Goat) (Cabbage Wolf))) (== q 'Succeed)))
'(Succeed)

The seen-group/o relation can also be used to find all the histories where a specific group was seen, but the output might be surprising. First, since there are an infinite number of histories which can contain a group, we’ll just get the first 5 here using (run 5 q ...):

1
2
3
4
5
6

> (run 5 q (seen-group/o '(Wolf Cabbage) q))
'(((Wolf Cabbage) . _.0)
  ((Cabbage Wolf) . _.0)
  (_.0 (Wolf Cabbage) . _.1)
  (_.0 (Cabbage Wolf) . _.1)
  (_.0 _.1 (Wolf Cabbage) . _.2))

The symbols _.0, _.1, _.2, etc stand for “any value”, so the list ’((Wolf Cabbage) . _.0) means a list whose first element is (Wolf Cabbage) followed by any tail value, that is, all lists which have (Wolf Cabbage) as the first element. Essentially, the answer for the histories which contain (Wolf Cabbage) are the all the lists which have that element in the first position, followed by all the lists that have the element in the second position and so on.

Of course, when we choose the next move, we want to pick a group that was NOT yet seen, and seen-group/o succeeds if a group was seen. Unfortunately, implementing “not” in a relational language has some challenges. We can easily implement not-seen-group/o such that it fails when seen-group/o succeeds, but this would break the symetry that we had in our relations so far:

1
2
3
4
5

(defrel (not-seen-group/o g history)
  ;; cond/u (instead of cond/a) is an optimization here, to avoid trying to
  ;; exhaust all `seen groups`
  (cond/u ((seen-group/o g history) fail)
          (succeed)))

The not-seen-group/o relation works as expected when both g and history are “known”, that is they have actual values, for example:

1
2
3
4

> (run 1 q (fresh () (not-seen-group/o '(Wolf) '((Goat) (Cabbage))) (== q 'Succeed)))
'(Succeed)
> (run 1 q (fresh () (not-seen-group/o '(Wolf) '((Goat) (Cabbage) (Wolf))) (== q 'Succeed)))
'()

… however, if we try to find what values are NOT in a history, or try to find what histories don’t contain a value, the relation does not work as expected:

1
2
3
4
5
6

;; Try to find groups NOT in the search history ...
> (run 1 q (not-seen-group1/o q '((Goat) (Cabbage) (Wolf))))
'()
;; Try to find search histories that don't contain the '(Wolf) group...
> (run 1 q (not-seen-group1/o '(Wolf) q))
'()

The problem is that there is no way to represent the value "a list without a specific element" in miniKanren (an extension of the language using absent/o is able to represent such lists). In our case, we don’t actually need this feature, but it is a good idea to protect the relation and report an error if the values are not grounded, since the fail the relation would return does not represent an actual failure and can be misleading:

1
2
3
4
5
6
7
8
9

(defrel (not-seen-group/o g history)
  (project (g history)
    (if (ground*? g)
        (if (ground*? history)
            succeed
            (error "not-seen-group/o: history is not ground"))
        (error "not-seen-group/o: g is not ground")))
  (cond/u ((seen-group/o g history) fail)
          (succeed)))

With these changes, not-seen-group/o still works as expected of both g and history are known, but it will report an error if the result cannot be determined (that is, when input values are not ground):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

> (run 1 q (fresh () (not-seen-group/o '(Wolf) '((Goat) (Cabbage))) (== q 'Succeed)))
'(Succeed)
> (run 1 q (fresh () (not-seen-group/o '(Wolf) '((Goat) (Cabbage) (Wolf))) (== q 'Succeed)))
'()
> (run 1 q (not-seen-group/o q '((Goat) (Cabbage) (Wolf))))
; not-seen-group/o: g is not ground
; Context (plain; to see better errortrace context, re-run with C-u prefix):
;   c:\Users\alexh\Projects\Racket\mk\mk.rkt:321:5
> (run 1 q (not-seen-group/o '(Wolf) q))
; not-seen-group/o: history is not ground
; Context (plain; to see better errortrace context, re-run with C-u prefix):
;   c:\Users\alexh\Projects\Racket\mk\mk.rkt:321:5

River Banks

We now need to define the last data structure for solving the puzzle: the River Bank. There are two river banks in the problem, a left and a right one, and each holds a group of participants; the objective of the puzzle is to find a crossing order between these two banks. For each river bank, we also need to track what the goal group is, that is, what end results are we aiming for when planning the trips, as well as a history of previous groups that we have seen so far, to avoid getting stuck in an infinite loop.

A river bank will be represented as a list, with the River-Bank symbol as the first element. Using a symbol as the first element in the list is not strictly required, but since the only data structure supported by miniKanren is the list, it is difficult to tell apart a “group” list and a “river bank” list and the River-Bank symbol serves to differentiate between the two.

Here is what the Left and Right banks look like at the start of the puzzle. For example, the left bank contains all the participants, the goal state is the empty group and the history contains the first group, since we don’t want to see that group again while planning the crossings:

1
2

'(River-Bank Left (Wolf Goat Cabbage) () ((Wolf Goat Cabbage)))
'(River-Bank Right () (Wolf Goat Cabbage) (()))

In general a river bank look like this:

1

'(River-Bank tag group goal history)

Where:

• River-Bank is a symbol identifying this as a River-Bank structure.
• tag is one of the Left or Right symbols — this will help telling the two river banks apart and construct plan steps that the user can understand
• group is the current group of participants on the bank, for example, (Goat Wolf Cabbage),
• goal is the goal group for each bank — this is used to check if we have completed the plan, for the Left, which starts with all the participants, this is the empty list (i.e. no participants left on that bank), for the right bank, which starts out empty, the goal is the full list of participants.
• history is a list of previous groups seen on the bank during the planning process — this starts out as an empty list.

We’ll need to write some relations to manipulate river bank structures, and the first one is goal-state/o which is used to determine if the goal was reached for a river bank, that is the “group” and “goal” are the same:

1
2
3
4

(defrel (goal-state/o state)
  (fresh (tag group goal history)
    (== `(River-Bank ,tag ,group ,goal ,history) state)
    (same/o group goal)))

Let’s see how this works:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

;; Current state is not a goal state:
> (run 1 q (fresh () 
             (goal-state/o '(River-Bank Left (Goat Cabbage Wolf) () ()))
             (== q 'Succeed)))
'()
;; Current state is the goal state:
> (run 1 q (fresh () 
             (goal-state/o '(River-Bank Left () () ()))
             (== q 'Succeed)))
'(Succeed)

Next, we’ll need a relation to pick a candidate from a river bank. We already have pick-maybe-nothing/o but that works on groups, which are list of participants, the pick-participant-from/o relation will use it to pick a candidate, ensuring that it was not already picked (by checking the history) and produce a new river bank structure with that participant removed and history updated::

1
2
3
4
5
6

(defrel (pick-participant-from/o state participant out)
  (fresh (tag group goal history updated-group)
    (== `(River-Bank ,tag ,group ,goal ,history) state)
    (pick-maybe-nothing/o group participant updated-group)
    (not-seen-group/o updated-group history)
    (== `(River-Bank ,tag ,updated-group ,goal (,updated-group . ,history)) out)))

Let’s see how this works: from a River-Bank with the Wolf and Cabbage, we can pick Nothing, the Wolf or the Cabbage — note how the history is updated in each case.

1
2
3
4

> (run* (q r) (pick-participant-from/o '(River-Bank Left (Wolf Cabbage) () ()) q r))
'((Nothing (River-Bank Left (Wolf Cabbage) () ((Wolf Cabbage))))
  (Wolf (River-Bank Left (Cabbage) () ((Cabbage))))
  (Cabbage (River-Bank Left (Wolf) () ((Wolf)))))

Once a participant was ferried accross the river, it needs to be added to that state, producing a new output state, and this is the role of the add-participant-to/o relation. Special care is taken not to add Nothing to the state — also we have to use cond/a instead of cond/e here, so only one of the “cond” branches produces values:

1
2
3
4
5
6
7

(defrel (add-participant-to/o state participant out)
  (cond/a
   ((== participant 'Nothing)
    (== out state))
   ((fresh (tag group goal history)
      (== `(River-Bank ,tag ,group ,goal ,history) state)
      (== `(River-Bank ,tag (,participant . ,group) ,goal ,history) out)))))

Let’s check that this works correctly, when we first try to add Nothing to a river bank and than try to add the Goat:

1
2
3
4

> (run* q (add-participant-to/o '(River-Bank Right () (Wolf Goat Cabbage) ()) 'Nothing q))
'((River-Bank Right () (Wolf Goat Cabbage) ()))
> (run* q (add-participant-to/o '(River-Bank Right () (Wolf Goat Cabbage) ()) 'Goat q))
'((River-Bank Right (Goat) (Wolf Goat Cabbage) ()))

Finally, the miniKanren program to solve the puzzle must produce a plan, which is a sequence of steps required to solve the puzzle. The plan is a list of steps, where each step is simply a list forming an English sentence, for example (Ferry Goat From Left To Right). Once an candidate has been picked from a river bank, the make-step/o relation will produce a plan step by simply taking the names of the participant and the two river banks:

1
2
3
4
5

(defrel (make-step/o from to participant step)
  (fresh (ftag fgroup fgoal fhistory ttag tgroup tgoal thistory)
    (== `(River-Bank ,ftag ,fgroup ,fgoal ,fhistory) from)
    (== `(River-Bank ,ttag ,tgroup ,tgoal ,thistory) to)
    (== `(Ferry ,participant From ,ftag To ,ttag) step)))

Here is how it works:

1
2
3
4
5
6

> (run* q (make-step/o
            '(River-Bank Left (Goat Wolf Cabbage) () ())
            '(River-Bank Right () (Goat Wolf Cabbage) ())
            'Goat
            q))
'((Ferry Goat From Left To Right))

We now have all the required miniKanren relations to plan the river crossing, lets do that next.

Planning the Crossing

With all the relations defined so far, all that remains is to define the constraints for planning process. The do-plan/o relation will construct a plan to move participants from a river bank to the other one:

• If the from state is already in the goal state, the plan is empty (i.e. nothing needs to be done), otherwise:
• Pick a participant, producing a new from river bank state updated-from
• Add that participant to the to river bank, producing a new state, updated-to
• Construct a step in the plan by collating the information with the participant and the name of the two river banks
• Add the step to the plan
• Construct the remaining of the plan by swapping the two river banks and calling do-plan/o recursively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(defrel (do-plan/o from to plan)
  (cond/e
   ((goal-state/o from)
    (== plan '()))
   ((fresh (participant step remaining updated-from updated-to)
      (pick-participant-from/o from participant updated-from)
      (add-participant-to/o to participant updated-to)
      (make-step/o from to participant step)
      (cons/o step remaining plan)
      (do-plan/o updated-to updated-from remaining)))))

Before we try it out, let’s write a helper relation which sets up the from and to river banks as the problem states them:

1
2
3
4
5
6
7

(defrel (wolf-goat-cabbage-plan/o plan)
  (let ([from '(Wolf Goat Cabbage)]
        [to '()])
    (do-plan/o
     `(River-Bank Left ,from ,to (,from))
     `(River-Bank Right ,to ,from (,to))
     plan)))

Running this last relation will produce a plan to ferry all participants safely across the river:

1
2
3
4
5
6
7
8

> (run 1 plan (wolf-goat-cabbage-plan/o plan))
'(((Ferry Goat From Left To Right)
   (Ferry Nothing From Right To Left)
   (Ferry Wolf From Left To Right)
   (Ferry Goat From Right To Left)
   (Ferry Cabbage From Left To Right)
   (Ferry Nothing From Right To Left)
   (Ferry Goat From Left To Right)))

We can even find that there are in fact two possible solutions to this puzzle, when asking for all the solutions using run*.

Final Thoughts

Looking at the plan/o relation, it appears to be a simple recursive definition: find the fist step of them plan than find the remaining steps until completed. There is no explicit backtracking, the relations appear to know how to pick the correct participant at each step — this is of course an illusion and the backtracking itself is built into miniKanren. Technically, miniKanren does not use backtracking, but it does keep track of all the alternatives for us and automatically retries other cond/e branches of one fails.

If you would like the entire program as a single file, it is available as a gist here.