IIn Prolog we can
represent a binary tree as either the atom nil (for the
empty tree) or as t(L, V, R), where V is the value at
the root and L and R are the left and right subtrees.
Write a Prolog predicate isTree(T) that is true if T
is a binary tree. (It does not need to be a binary search tree;
values can appear in any order and can have any type).
Write a predicate sum(T, N) that is true if T is a
binary tree of integers and N
is the sum of the integers in the tree.
Write a Prolog predicate leaves(T, S) that is true if
S is a list of values in the leaves of the binary tree T.
Recall that a leaf is a node with no chlidren. Ideally
your predicate will run in time O(|S|). Your predicate should work in
both directions.
Write a Prolog predicate symmetrical(T) that is true
if T is a symmetrical binary tree: its left-to-right reflection is
itself.
Write a Prolog predicate is_search_tree(T) that
succeeds if T is a binary tree of integers that satisfies the
ordering requirements of a binary search tree: for
any node N has value V, every value in N's left subtree has a
value that is less than V, and every value in N's right subtree has a
value that is greater than V.
A monkey is standing in a room at position pos_a. There is a box at position pos_b. A bunch of bananas are hanging from the ceiling at position pos_c.
The monkey may take the following actions:
go(P) – go to position P
push(P) – push the box (which must be at the monkey's current position) to position P
climb_on – climb onto the box (which must be at the monkey's current position)
climb_off – climb off the box (only if the monkey is currently on the box)
grab – grab the bananas (only if the monkey is on the box under the bananas)
The monkey would like to eat the bananas. Write a Prolog program that can generate all possible solutions, in increasing order of length. A solution is a list of actions to reach the goal.
Can we place N queens on a chessboard so that none of them attack any other?
Write a predicate queens(N, L) that is true if L is a
solution to the N-queens problem. L will
be a list of integers from 1 to N representing the row
position of the queen in each column. Your predicate should be able
to check and generate solutions.
A magic square is a square of size N x N that contains all integers from 1 .. N2 and in which every row, column and diagonal adds to the same value.
Write a Prolog predicate that can test whether a square is magical. When run backward, it should also be able to generate magic squares of a given size.
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.
Three jugs have capacity 8, 5 and 3 liters. These are initially filled with 8, 0 and 0 liters. We wish to find a way to pour water between the jugs so that some jug will have 4 liters of water. Write a Prolog program to find the shortest possible solution.
Suppose that we have a set of blocks, each with a given width, height and depth. We want to know whether they can be packed into a box with a given width, height and depth. The blocks may not be rotated.
We will represent a block as a structure block(X, Y, Z, DX,
DY, DZ), where (X, Y, Z) is the block's position, and (DX, DY,
DZ) is its width, height and depth.
Write a predicate pack(Blocks, Box) that is true if
the blocks will fit. For example,
pack([block(X1, Y1, Z1, 2.0,
1.0, 4.0),
block(X2, Y2, Z2, 1.0,
3.0,
4.0)], box(3.0, 3.0, 5.0)]
is true and will return a set of valid block positions.
Modify your solution to the previous exercise so that blocks may be rotated in any direction in 90-degree increments.