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.
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.
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.
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.