1. Tree Leaves

Write a Prolog predicate leaves(?T, ?S) that is true if S is a list of leaves of the binary tree T. Be sure that your predicate will run in time O(|S|).

2. Binary Search Tree

Write a Prolog predicate insert(+T, +K, ?T1) that inserts a value K into a binary search tree T, yielding tree T1.

3. Graph Path

Write a Prolog predicate path(+G, +V, +W, ?L) that is true if L is a path from V to W in the directed graph G. The graph may contain cycles, so be sure not to walk in a loop forever.

4. Wolf, Goat, Cabbage

A farmer is on the south bank of a river with a wolf, a goat, and a cabbage. He has a boat that can hold him plus any one of these three items. If the wolf and goat are left alone without the farmer, the wolf will eat the goat. If the goat and cabbage are left alone without the farmer, the goat will eat the cabbage. The wolf does not like cabbage.

How can the farmer cross with all of these possessions to the north bank? Write a Prolog program that can determine the shortest solution.

5. Water Jugs

We have three jugs with capacity 8, 5, and 3 liters. Initially the first jug is full of water, and the others are empty.

We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.

What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?

Write a Prolog program that can find the shortest possible sequence.