Project 2: Foxes and Hens Puzzle

CMSC 330, Sections 0201/0202

written by Michael L. Scott, edited by Vibha Sazawal

Note:If you choose to work with a project partner, you must choose someone that is in your section. I strongly recommend that you work with someone else on this project.

You are to write a simple program in Prolog to solve the following puzzle: In a children's story, three foxes and three hens are traveling together. They come to a river they must cross. There is a boat, but it will hold no more than two of them at a time. Thus, there must be multiple trips across the river, and at least one animal must row the boat back to the left side of the shore, before the next trip from left to right can commence. The problem is that the hens cannot trust the foxes; if in the process of crossing the river we ever end up with more foxes than hens on either shore, the foxes are likely to eat the hens. We need a series of moves (trips across the river in the boat) that will get the entire party across safely. Any animal that boards the boat lands on the other side of the river. There is no notion of an animal "staying on the boat." An animal is either on the left side or the right side of the river.

Part One: due April 29th, 11:59 PM

For now, assume there are only TWO foxes and TWO hens. For this simpler problem, the trip can be completed in five boat trips. We can describe the five boat trips using 6 lists. Each list describes the "configuration" on the left hand side of the river. The first list is [2,2,1]. That means there are 2 foxes on the left hand side of the river, 2 hens of the left side of the river, and 1 boat on the left side of the river. In general, configurations take the form [#F on left side, #H on left side, #B on left side]. The second list describes the state of the left side of the river after the first boat trip. If, for example, the first boat trip included 1 fox and 1 hen, the second list would be [1,1,0]. The sixth list is the last configuration on the left side, which should be [0,0,0] (because all animals and the boat are now on the right side of the river).

Your main predicate should be a goal named foxhen(First, Second, Third, Fourth, Fifth, Sixth). First should be the first configuration of the left hand side and Sixth should be the last configuration of the left hand side.

If you request additional solutions (by typing a semicolon) the interpreter should give you additional lists. Redundant answers are ok (for Part 1), as long as all correct answers eventually get printed.

You are not permitted to use asserta, assertz, retract, or other database-modifying predicates. You can only tell Prolog to consult your file and then ask the foxhen query. For the record, you must compute your solutions. You are not allowed to figure them out by hand and simply write a program that prints them!

If your answer exceeds 50 lines of code and/or 6 predicates, you are probably on the wrong track.

Part Two: due May 11th, 11:59 PM

Now provide a solution for THREE foxes and THREE hens. Your main predicate should be a goal solve(P). It should instantiate P to be a list of configurations, each of which indicates the location of the animals and the boat. As in Part 1, we will represent a configuration as the number of foxes, hens, and boats on the near (left) shore: [LF, LH, LB], where 0 <= LF <= 3, 0 <= LH <= 3, and 0 <= LB <= 1. Unlike our foxhen predicate in Part 1, solve only takes ONE ARGUMENT, which is a list of the configurations. Thus P should look like [[LF, LH, LB], [LF, LH, LB], ... ]. The first element of P should be [3,3,1], and the last element of P should be [0,0,0].

You can think of the state space of this problem as a graph in which nodes are configurations and edges represent feasible boat trips. It's a large graph, however, and you won't want (nor in fact are you permitted) to represent it explicitly in your Prolog database. From any given state you'll need to figure out the set of possible neighbors to explore. You'll also want to keep track of where you have been, so you don't get stuck in a cycle.

If you request additional solutions (by typing a semicolon) the interpreter should give you additional lists, as many as there are UNIQUE solutions. For Part 2, no redundant answers are permitted.

You are not permitted to use asserta, assertz, retract, or other database-modifying predicates. You can only tell Prolog to consult your file and then ask the solve query. You must compute your solutions. You are not allowed to figure them out by hand and simply write a program that prints them!

Also, for Part 2, you CANNOT "hard-code" in the number of configurations expected in the answer as we did in Part 1.

Additional Instructions (applicable for Part 1 and Part 2)

I will run your code using gprolog on linuxlab.
Put all of your code in one file named "foxhen.db". Using gprolog, I will use consult to load your database. Then I will ask the query foxhen (for Part 1) or solve (for Part 2).
For references, you can use the GProlog Manual.
DO NOT USE any other Internet sources.
DO NOT SHARE code with anyone other than your project partner. You may work with one 330 student who is also in your section.
If you use code from 330 lecture, document that in a comment.

Deadlines

April 29th, 11:59 PM: Using the submit server, upload one file named "foxhen.db". The file must have a fully working version of the foxhen predicate for 2 foxes and 2 hens.
May 11th, 11:59 PM: Using the submit server, upload one file named "foxhen.db". The file must have a fully working version of the solve predicate for 3 foxes and 3 hens. solve's argument is a single list.