Backtracking in ABC: The Budd Challenge

Steven Pemberton, CWI, Amsterdam

Table of Contents


Introduction

In his article "(Extremely) Simple Logic Programming in B" [1], Tim Budd presented a program in B (the forerunner of ABC) for solving the "Farmer, Wolf, Goat and Cabbage in a boat trying to get to the other side of the river without eating each other" problem. The problem involves the four named trying to cross a river with a boat that can only take two of them at a time, with the added complication that only the farmer can row, and that the goat will eat the cabbage, and the wolf will eat the goat, if they are left without the farmer's supervision.

Tim's program uses backtracking, and in the way it is formulated takes advantage of the fact that functions in B have no side-effects, in effect doing the backtracking automatically for you. However, the program does have the 'side effect' of writing the results out as it goes along, rather than returning the result. When pointing this out, Tim says:

In other words, if the effect you want to have is more than just writing your answer out, bad luck.

The purpose of this article is to show that it is not at all difficult to write such a program, both using ABC's automatic backtracking and returning a result.

Just for interest's sake, I shall also modify some other aspects of Tim's program, to compare how different approaches to data-structures affect the program, but this in no way affects the main point of the article, which is to demonstrate returning results in a backtracking program.

A Solution

First of all, I'm going to alter how the positions of the participants are represented: Tim used a compound like (1, 1, 1, 1) to represent all four participants being on the north bank: each field was the position of one participant in the order: farmer, wolf, goat, cabbage; a zero represented the south bank.

Rather than represent north and south by 1 and 0, I shall use the texts "N" and "S" (I would have used "north" and "south", but this makes some of the lines below wider than will fit on the page). Tim said that he chose the integers to make the conversion from one to the other easier. For the text representation, we have to alter the definition of the function opposite:

HOW TO RETURN opposite position:
   RETURN {["N"]: "S"; ["S"]: "N"}[position]

Just to test it:

>>> WRITE opposite "N"
S
>>> WRITE opposite "S"
N

(Alternatively, a global target could contain the above table, and be SHAREd wherever needed.)

Now a more explicit data-structure can be used to represent the positions, such as a table:

{["cabbage"]: "N"; ["farmer"]: "N"; ["goat"]: "N"; ["wolf"]: "N"}.

Next we need an easy method of altering the set of positions when a boat-load goes to the opposite bank. If we represent a boat-load by a list of who is in the boat, for instance {"farmer"; "goat"} then we can use the following function to take a position and a list of travellers and return the new position:

HOW TO RETURN position altered.for occupants:
   FOR occupant IN occupants:
      PUT opposite position[occupant] IN position[occupant]
   RETURN position
>>> PUT {} IN start
>>> FOR participant IN {"farmer"; "goat"; "wolf"; "cabbage"}:
       PUT "N" IN start[participant]
>>> WRITE start altered.for {"farmer"; "goat"}
{["cabbage"]: "N"; ["farmer"]: "S"; ["goat"]: "S"; ["wolf"]: "N"}

We also need a way to see if a given position is 'safe', that is to say that the goat is not left alone with the cabbage, and that the wolf is not left alone with the goat:

HOW TO REPORT safe pos:
   REPORT farmer.with.goat OR goat.out.of.mischief
farmer.with.goat:
   REPORT pos["farmer"] = pos["goat"]
goat.out.of.mischief:
   REPORT pos["cabbage"] <> pos["goat"] <> pos["wolf"]

(Notice the shorthand c<>g<>w instead of c<>g AND g<>w. Another way of writing the same is g not.in {c; w}.)

Now, the new version of the program to solve the river problem, instead of printing out its results as it goes along, will return the answer as a value. This result is a sequence of boat-loads necessary to solve the problem.

Sequences are typically represented in ABC as tables with the elements of the sequence as items, and integers as keys. Elements are then added to the sequence with a command such as

PUT element IN sequence[#sequence]

so that the first element is stored at key [0], the second at [1], and so on.

In this program, the result is a sequence of boat-loads and so it will be represented as a table with integers as indexes, and boat-loads as elements. The only difference is that the boat-loads are produced by the program in reverse order to how they will be printed out, and so the elements will be added at the head of the sequence. This can be done with the command PUT element IN path[-#path], which we can make into a function:

HOW TO RETURN path with element:
   PUT element IN path[-#path]
   RETURN path

An example of a sequence of boat-loads is

{[-2]: {"farmer"; "goat"}; [-1]: {"farmer"}; [0]: {"wolf"; "farmer"}}

representing the farmer taking the goat across the river, returning alone, and then taking the wolf.

The program either succeeds, and produces such a path, or the (sub-)problem has no solution, and so it should fail. To represent these two cases, the program returns a compound, consisting of a text, either "success" or "failure" indicating whether it has succeeded or not, and then the path, empty for failure, and the solution for success. (At first I had the program only return a path, and used an 'impossible' path, such as {[1]: {}} to represent failure. I quickly saw this as a typical programmer's kludge, and replaced it with the cleaner solution here.). To make life easier, let's have a command to print out the result (this is just a simple version, it could be made prettier):

HOW TO PRINT result.and.path:
   PUT result.and.path IN result, path
   SELECT:
      result = "failure":
         WRITE "No solution" /
      ELSE:
         FOR move IN path:
            WRITE "Move", move /

The original program took as parameter the target position of the four, and then searched backwards to see if there was a way that that position could be reached from the start position (which was 'hard-wired' in the program). It was necessary to search backwards, because, like the new version, it produced its answers backwards, and so the two backwardses cancelled each other out. Another change I have made to the original program is to make both the start and the target positions parameters, and to make the program search from the start position for a path to the target position. As I have already said, it produces its answers backwards, but stores them in the result backwards, so that they still come out the right way round.

The final change is that now 'allowable' boat-loads are not hard-wired in the program, but represented as a list: a maximum of two can fit in the boat (it's a very large cabbage), and furthermore only the farmer can row:

>>> PUT {} IN allowable
>>> INSERT {"farmer"} IN allowable
>>> FOR other IN {"cabbage"; "goat"; "wolf"}:
       INSERT {"farmer"; other} IN allowable

We can now write a function that returns which boat-loads are possible from the current position:

HOW TO RETURN possible.from position:
   SHARE allowable
   PUT {} IN result
   FOR boat.load IN allowable:
      IF EACH occupant IN boat.load HAS on.same.side:
         INSERT boat.load IN result
   RETURN result
on.same.side:
   REPORT position[occupant] = position[min boat.load]

So now, after that introduction to the data-types, we can see the program proper. You'll notice comparing it with Tim's original, that the main body is more or less the same, except that results are being returned rather than tests being reported. The main difference is in the refinement to try the next move. Tim's program tried each of four refinements until one succeeded. The new version tries each of the allowable boat-loads until one succeeds. If none succeeds, it fails. A marginal issue is how to treat the case where the aim is reachable, but not safe in itself. Tim's version accepted it, and printed the result; this version by reversing the order of the first two IF commands, does not accept it.

HOW TO RETURN position path.to aim:
   SHARE looking
   IF position in looking OR NOT safe position: RETURN failure
   IF position = aim: RETURN success
   INSERT position IN looking
   RETURN next.move
next.move:
   FOR boat.load IN possible.from position:
      PUT new.position path.to aim IN result, path'
      IF result <> "failure": RETURN result, path' with boat.load
   RETURN failure
new.position: RETURN position altered.for boat.load
success: RETURN "success", {}
failure: RETURN "failure", {}

(Remember that looking is used to prevent the program searching for a solution to a position it is already trying to solve -- otherwise you can get an infinite loop.) Now to try it out:

>>> PUT {}, {} IN start, aim
>>> FOR occupant IN {"farmer"; "goat"; "wolf"; "cabbage"}:
       PUT "N", "S" IN start[occupant], aim[occupant]
>>> PUT {} IN looking
>>> PRINT start path.to aim
Move {"farmer"; "goat"}
Move {"farmer"}
Move {"cabbage"; "farmer"}
Move {"farmer"; "goat"}
Move {"farmer"; "wolf"}
Move {"farmer"}
Move {"farmer"; "goat"}

Now to try it with a different aim: the farmer has to get the cabbage to the other side (to sell it to the hungry computer programmer who lives there):

>>> PUT start IN aim
>>> PUT "S" IN aim["cabbage"]
>>> PRINT start path.to aim
Move {"farmer"; "goat"}
Move {"farmer"}
Move {"cabbage"; "farmer"}
Move {"farmer"; "goat"}

Now, finally, the farmer is fed up with goats, cabbages and wolves, and wants to be alone on the other side:

>>> PUT start IN aim
>>> PUT "S" IN aim["farmer"]
>>> PRINT start path.to aim
No solution

Alas, poor farmer.

Producing the result forwards

The question arises as to why the program produces the result backwards. The answer for Tim's version of the program is that you don't know until you've reached the goal whether the current position is on a successful path, and so you can't write anything until then. With the new version you do have the option of producing the results forwards. To do it you have to pass to path.to not only the current position, but how you got to it (as a path). Just to show you how it would look, here is path.to altered in that way. The function with would also have to be altered to append elements to the path, rather than prepend them.

HOW TO RETURN (route, position) path.to aim:
   SHARE looking
   IF position in looking OR NOT safe position: RETURN failure
   IF position = aim: RETURN success
   INSERT position IN looking
   RETURN next.move
next.move:
   FOR boat.load IN possible.from position:
      PUT (new.route, new.position) path.to aim IN result, path'
      IF result <> "failure": RETURN result, path'
   RETURN failure
new.route: RETURN route with boat.load
new.position: RETURN position altered.for boat.load
success: RETURN "success", route
failure: RETURN "failure", {}

You would then have to call it as

PRINT ({}, start) path.to aim

However, you may notice that route here contains more or less the complementary information to what looking contains. If you represent a path as the sequence of positions, instead of the sequence of moves, you can do away with looking altogether, with the choice of SHAREing route or passing it as a parameter:

HOW TO RETURN (route, position) path.to aim:
   IF position in route OR NOT safe position: RETURN failure
   PUT route with position IN route
   IF position = aim: RETURN success
   RETURN next.move
next.move:
   FOR boat.load IN possible.from position:
      PUT (route, new.position) path.to aim IN result, path'
      IF result <> "failure": RETURN result, path'
   RETURN failure
new.position: RETURN position altered.for boat.load
success: RETURN "success", route
failure: RETURN "failure", {}

This means that you get as output the states rather than the moves you have to make:

>>> PRINT ({}, start) path.to aim
{["cabbage"]: "N"; ["farmer"]: "N"; ["goat"]: "N"; ["wolf"]: "N"}
{["cabbage"]: "N"; ["farmer"]: "S"; ["goat"]: "S"; ["wolf"]: "N"}
{["cabbage"]: "N"; ["farmer"]: "N"; ["goat"]: "S"; ["wolf"]: "N"}
{["cabbage"]: "S"; ["farmer"]: "S"; ["goat"]: "S"; ["wolf"]: "N"}
{["cabbage"]: "S"; ["farmer"]: "N"; ["goat"]: "N"; ["wolf"]: "N"}
{["cabbage"]: "S"; ["farmer"]: "S"; ["goat"]: "N"; ["wolf"]: "S"}
{["cabbage"]: "S"; ["farmer"]: "N"; ["goat"]: "N"; ["wolf"]: "S"}
{["cabbage"]: "S"; ["farmer"]: "S"; ["goat"]: "S"; ["wolf"]: "S"}

However, for the rest of this article I will stick with the reverse method.

Another possible representation

You may remark in path.to that there is no dependency within the how-to on exactly how a position is represented. What would we have to change if we represented it as, for instance, {["N"]: {"farmer"; "goat"}; ["S"]: {"cabbage"; "wolf"}}, a representation that more closely represents the real state of affairs?

Well, the main change would come in altered.for, which would look like this:

HOW TO RETURN positions altered.for occupants:
   FOR occupant IN occupants:
      SELECT:
         SOME place IN keys positions HAS occupant in positions[place]:
            REMOVE occupant FROM positions[place]
            INSERT occupant IN positions[opposite place]
   RETURN positions
>>