Lab 3: Application of Constraint Satisfaction Problems in Prolog
Task 1: Monkey-Banana Problem:
Premises:
➢ Monkey wants to eat banana but can’t reach them.
➢ A hungry monkey is in room.
➢ Suspended from the roof, just out of his reach, is a bunch of bananas.
➢ In the corner of a room is a box. The monkey desperately wants to grasp bananas.
Solution:
Monkey walks to the box, pushes it under the bananas. Climbs on the box and picks the bananas and eats
them.
Code:
on(monkey, floor).
on(box, floor).
in(monkey, room).
in(box, room).
in(banana, room).
at(banana, ceiling).
strong(monkey).
grasp(monkey).
climb(monkey, box).
push(monkey, box):- strong(monkey).
under(banana, box):-push(monkey, box).
canreach(monkey, banana):- at(banana, floor); at(banana, ceiling),under(banana,box),climb(monkey,
box).
canget(monkey,banana):-canreach(monkey, banana), grasp(monkey).
Query:
? canget(monkey, banana).
True
?- trace.
true.
[trace] ?- trace.
true.
[trace] ?- canget(monkey, banana).
Call: (8) canget(monkey, banana) ? creep
Call: (9) canreach(monkey, banana) ? creep
Call: (10) at(banana, floor) ? creep
Fail: (10) at(banana, floor) ? creep
Redo: (9) canreach(monkey, banana) ? creep
Call: (10) at(banana, ceiling) ? creep
Exit: (10) at(banana, ceiling) ? creep
Call: (10) under(banana, box) ? creep
Call: (11) push(monkey, box) ? creep
Call: (12) strong(monkey) ? creep
Exit: (12) strong(monkey) ? creep
Exit: (11) push(monkey, box) ? creep
Exit: (10) under(banana, box) ? creep
Call: (10) climb(monkey, box) ? creep
Exit: (10) climb(monkey, box) ? creep
Exit: (9) canreach(monkey, banana) ? creep
Call: (9) grasp(monkey) ? creep
Exit: (9) grasp(monkey) ? creep
Exit: (8) canget(monkey, banana) ? creep
true.
Task 2: River Crossing Problem
Premises:
➢ A farmer wants to cross a river and take with him a wolf, a goat, and a cabbage.
➢ There is a boat that can fit himself plus either the wolf, the goat or the cabbage.
➢ If the wolf and the goat are alone on one shore, the wolf will eat the goat. If the goat and the
cabbage are alone on the shore, the goat will eat the cabbage.
➢ How can the farmer bring the wolf, the goat, and the cabbage across the river?
Solution:
Code:
other_bank(e,w).
other_bank(w,e).
%farmer,wolf,goat,cabbage
move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]):-other_bank(X,Y).
move([X,Wolf,X,Cabbage],goat,[Y,Wolf,Y,Cabbage]):-other_bank(X,Y).
move([X,Wolf,Goat,X],cabbage,[Y,Wolf,Goat,Y]):-other_bank(X,Y).
move([X,Wolf,Goat,Cabbage],farmer,[Y,Wolf,Goat,Cabbage]):-other_bank(X,Y).
safety_check(X,X,_).
safety_check(X,_,X).
safe_status([Man,Wolf,Goat,Cabbage]):-
safety_check(Man,Goat,Wolf),safety_check(Man,Goat,Cabbage).
solution([e,e,e,e],[]).
solution(Config,[Move|OtherMoves]):-
move(Config,Move,NextConfig),safe_status(NextConfig),solution(NextConfig,OtherMoves).
%length(X,7),solution([w,w,w,w],X).
Query:
?- length(X,7),solution([w,w,w,w],X).
X = [goat, farmer, wolf, goat, cabbage, farmer, goat] .
Task 3: Tower of Hanoi
Premises:
➢ The ancient puzzle of the Tower of Hanoi consists of some wooden disks and three poles attached
to a baseboard.
➢ The disks each have different diameters and a hole in the middle large enough for the poles to
pass through.
➢ The object of the puzzle is to move all the disks over to the right pole, one at a time, so that they
end up in the original order on that pole.
➢ The middle pole may be used as a temporary resting place for disks, but at no time is a larger disk
to be on top of a smaller one.
➢ The Tower of Hanoi problem can be easily solved with one or two disks but becomes more difficult
with three or more disks.
Solution:
✓ A simple strategy for solving the puzzle is –:
1. A single disk can be moved directly.
2. N disks can be moved in three steps:
i. Move N-1 disks to the middle pole.
ii. Move the last disk directly over to the right pole.
iii. Move the N-1 disks from the middle pole to the right pole.
For example :
move(3, source, target, auxiliary).
• Move top disk from source to target
• Move top disk from source to auxiliary
• Move top disk from target to auxiliary
• Move top disk from source to target
• Move top disk from auxiliary to source
• Move top disk from auxiliary to target
• Move top disk from source to target
Code:
move(1,X,Y,_) :- write('Move top disk from '),
write(X),
write(' to '),
write(Y),
nl.
move(N,X,Y,Z) :- N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
Query:
?-move(3,source,destination,interm).
Move top disk from source to destination
Move top disk from source to interm
Move top disk from destination to interm
Move top disk from source to destination
Move top disk from interm to source
Move top disk from interm to destination
Move top disk from source to destination
True
