Write a predicate digits(L, B, N) that is true if L is a list of digits in base B whose value is N. For example, digits([3, 4, 5], 10, 345) is true. Use a left fold.
Write the library predicate foldl(+P, ?L, ?A, ?R) using call().
Write a predicate foldr(+P, ?L, ?A, ?R) that performs a right fold over the values in L. For example, foldl(P, [x, y, z], A, R) will apply
P(z, A, A1), P(y, A1, A2), P(x, A2, R).
Consider binary trees represented as nil (the empty tree) or as t(L, X, R), where L and R are left and right subtrees. Write a predicate height(?T, ?H) that is true if H is the height of the binary tree T. Recall that the height of a tree is defined as the maximal distance from the root to any leaf. Your predicate should be able to generate all possible trees of any height.
a) Write a predicate foldr_tree(+P, ?T, ?A, ?R) that performs a right fold of a predicate over all values in a tree.
b) Write a predicate flatten(?T, ?L) that flattens a tree using foldr_tree().
Write a predicate insert(X, T, T1) that inserts a value X into a binary search tree T, producing a tree T1. If the value X is already in the tree T, then T1 should equal T.
Is it possible to delete values from a tree by running insert() backwards? Why or why not?
In this cryptarithmetic puzzle, every letter stands for a different digit:
A P P L E + G R A P E + P L U M =========== B A N A N A
Write a Prolog program that can find a solution to the puzzle.
Is it possible to place N queens on an N x N chessboard such that no two queens attack each other? Write a Prolog program that can solve this problem for any N.
Write a predicate bfs(+G, +V, +W, ?P) that finds the shortest path from vertex V to vertex W in an undirected graph. Use a breadth-first search.
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.
Write a predicate hamiltonian(+G, ?P) that takes an undirected graph in adjacency list representation and succeeds if P is a Hamiltonian path in G, i.e. a path that visits all vertices exactly once.
You could test your predicate on this graph:
graph(G) :- G = [ a -> [c, e], b -> [d, e], c -> [a, d, f],
d -> [b, c, e, f], e -> [b, d, f], f -> [c, d, e, g],
g -> [f] ]Write a predicate colorable(+G, +N) that takes an undirected graph in adjacency list representation and a positive integer N. The predicate should succeed if the graph is N-colorable, i.e. it is possible to assign one of N colors to each vertex in such a way that no adjacent vertices have the same color.
Write a predicate isomorphic(+G, +H) that takes two graphs in adjacency list representation and succeeds if the graphs are isomorphic.
Suppose that we have a set of rectangles, each with a given width and height. We want to know whether they can be packed into a rectangle R with a given width and height and depth. The rectangles may not be rotated.
We will represent a rectangle
as a structure rect(Width,
Height).
Write a predicate pack(L,
R,
Positions) that is true if the
rectangles
in list L can be packed into the rectangle R at the given list of
positions. A rectangle's position pos(X, Y) is
the position of its upper-left corner relative to the upper-left
corner of rectangle R.
Modify
your solution to the previous exercise so that the rectangles
in list L may be rotated by 90 degrees as they are packed into R. Now
each position should have the form pos(X, Y, R),
where R
= rot if
the rectangle has been rotated by 90 degrees, otherwise R
= not.
Write a higher-order predicate solve(+Move, +Start, +Goal) that can find the shortest path from a start state to an end state in any state space. Move(+S, ?T) should be a predicate that succeds if it's possible to move from state S to state T. Goal(+S) should be a predicate that's true if state S is a goal state.
Three missionaries and three cannibals wish to cross a river using a boat that can carry only two people. At no time may the cannibals outnumber the missionaries on either river bank, since then they would eat the missionaries. How can they cross? Write a Prolog program that can find the shortest solution.
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. 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 to find the shortest possible solution.
Four people wish to cross a river using a narrow bridge, which can hold only two people at a time. They have one torch and, because it's night, the bridge crossers must take the torch.
Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. Can they all get across the bridge if the torch lasts only 15 minutes? Write a Prolog program that can determine the answer.