Suppose that we have a functional queue implementation with the following predicates:
empty_queue(Q)
enqueue(X, Q, R) – enqueue X onto Q to make queue R
dequeue(X, Q, R) – dequeue X from Q to make queue R
Write the following predicates:
a) enqueue_all(L, Q, R) – enqueue all values in L onto Q to make queue R
b) dequeue_n(N, Q, L, R) – dequeue N values from Q, producing a list of values L plus queue R
Write the library function foldl(+Goal, ?L, ?A, ?R) using call().
We may represent a binary tree using 'nil' for the empty tree, and 't(L, X, R)' for a node with value X and children L and R.
Write a predicate flatten(T, L) that succeeds if L is a list of all the values in T. When given a tree with N nodes, your predicate should run in O(N).
Write a function foldltree(+Goal, ?T, ?A, ?R) that performs a left fold of a predicate over all values in a tree.
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
Additionally, no leading digit may be zero.
Write a Prolog program that can find a solution to the puzzle.
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.
Is it possible to place eight queens on a chessboard such that no two queens attack each other? Write a Prolog program that can solve this problem.
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 isomorphic(+G, +H) that takes two graphs in adjacency list representation and succeeds if the graphs are isomorphic.
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 path(+G, +V, +W, ?P) that finds the shortest path from vertex V to vertex W in an undirected graph. Use a breadth-first search.
Consider this trivial state space search problem. There are N coins on a table, initially all heads up. We want to make the shortest possible sequence of flips so that all coins will be tails up.
a) Write a predicate that finds a solution using iterative deepening.
b) Write a predicate that finds a solution using a breadth-first search.
c) Compare the performance of your two predicates.
Modify your solution to the previous exercise so that it uses an AVL tree to store the visited set. Use the 'assoc' library in SWI-Prolog. How does this affect your program's performance?
Write a higher-order predicate solve(+Move, +Start, +End) 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.
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.