COMP4418: Knowledge Representation and Reasoning
Introduction to Prolog III Problem Solving
Maurice Pagnucco
School of Computer Science and Engineering University of New South Wales
NSW 2052, AUSTRALIA morri@cse.unsw.edu.au
Reference: Ivan Bratko, Prolog Programming for Artificial Intelligence, Addison- Wesley, 2001. Chapter 4.
COMP4418 ⃝c UNSW, 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 1
Graph Search in Prolog
345
6
18
27
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 2
Binary Trees
A graph may be represented by a set of edge predicates and a list of vertices
edge(1, 5).
edge(2, 1).
edge(3, 1).
edge(4, 3).
edge(5, 8).
edge(6, 4).
edge(7, 5).
edge(8, 6).
vertices([1, 2, 3, 4, 5, 6, 7, 8]).
edge(1, 7).
edge(2, 7).
edge(3, 6).
edge(4, 5).
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
edge(6, 5).
edge(8, 7).
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 3
Finding a Path
Write a program to find a path from one node to another
Must avoid cycles (i.e., going around in a circle)
A template for the clause is
path(Start, Finish, Visited, Path).
Start is the name of the starting node
Finish is the name of the finishing node
Visited is the list of nodes already visited
Start is the list of nodes on the path, including Start and Finish
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 4
The path Program
The search for a path terminates when we have nowhere to go
path(Node, Node, _, [Node]).
A path from Start to Finish starts with a node, X, connected to
Start followed by a path from X to Finish
path(Start, Finish, Visited, [Start|Path]) :- edge(Start, X),
not(member(X, Visited)),
path(X, Finish, [X|Visited], Path).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 5
Hamiltonian Paths
A Hamiltonian path is a path which spans the entire graph without any repetition of nodes in the path
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
hamiltonian(P) :-
vertices(V),
member(S, V),
path(S, _, [S], P),
subset(V, P).
subset([], _) :- !.
subset([A|B], C) :-
member(A, C),
subset(B, C).
: hamiltonian(P)?
P = [2, 1, 7, 5, 8, 6, 4, 3]
P = [2, 7, 5, 8, 6, 4, 3, 1]
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 6
Missionaries and Cannibals
There are three missionaries and three cannibals on the left bank of a river
They wish to cross over to the right bank using a boat that can only carry two at a time
The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibal’s dinner
Plan a sequence of crossings that will take everyone safely across
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 7
Representing the State
A state is one “snapshot” in time
For this problem, the only information we need to fully characterise
the state is:
◮ the number of missionaries on the left bank ◮ the number of cannibals on the left bank
◮ the side the boat is on
All other information can be deduced from these three items
In Prolog, the state can be represented by a 3-ary term,
state(Missionaries, Cannibals, Side)
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 8
Representing the Solution
The solution consists of a list of moves, e.g., [move(1, 1, right), move(2, 0, left)]
which we will take to mean that 1 missionary and 1 cannibal moved to the right bank, then 2 missionaries moved to the left bank
Like the graph search problem, we must avoid returning to a state we have visited before
The visited list will have the form: [MostRecentState | ListOfPreviousStates]
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 9
Overview of Solution
We follow a simple graph search procedure
◮ Start from an initial state
◮ Find a neighbouring state
◮ Check that the new state has not been visited before ◮ Find a path from the neighbour to the goal
The search terminates when we have found the state: state(0, 0, right).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 10
Top-level Prolog Code
COMP4418
⃝c UNSW, 2019 Generated: 15 September 2019
% mandc(CurrentState, Visited, Path)
mandc(state(0, 0, right), _, []). mandc(CurrentState, Visited, [Move|RestOfMoves]) :-
newstate(CurrentState, NextState), not(member(NextState, Visited)), make_move(CurrentState, NextState, Move), mandc(NextState, [NextState|Visited], RestOfMoves).
make_move(state(M1,C1,left), state(M2,C2,right), move(M,C,right)) :- M is M1 – M2,
C is C1 – C2.
make_move(state(M1,C1,right), state(M2,C2,left), move(M,C,left)) :- M is M2 – M1,
C is C2 – C1.
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 11
Possible Moves
A move is characterised by the number of missionaries and the number of cannibals taken in the boat at one time.
Since the boat can carry no more than two people at once, the only possible combinations are:
carry(2, 0).
carry(1, 0).
carry(1, 1).
carry(0, 1).
carry(0, 2).
Wherecarry(M,C)meanstheboatwillcarryMmissionariesandC cannibals on one trip
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 12
Feasible Moves
Once we have found a possible move, we have to confirm that it is feasible
I.e., it is not feasible to move more missionaries or more cannibals than are present on one bank
Whenthestateisstate(M1,C1,left)andwetrycarry(M,C) then
M <= M1andC <= C1 must be true
When the state is state(M1, C1, right) and we try carry(M, C) then
M + M1 <= 3 and C + C1 <= 3 must be true
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 13
Legal Moves
Once we have found a feasible move, we must check that it is legal I.e., no missionaries must be eaten
COMP4418
⃝c UNSW, 2019 Generated: 15 September 2019
legal(X, X) :- !.
legal(3, X) :- !.
legal(0, X).
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 14
Generating the Next State
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
newstate(state(M1, C1, left), state(M2, C2, right)) :- carry(M, C),
M <= M1,
C <= C1,
M2 is M1 - M,
C2 is C1 - C,
legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :- carry(M, C),
M2 is M1 + M,
C2 is C1 + C,
M2 <= 3,
C2 <= 3,
legal(M2, C2).
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 15
Logic Puzzles
Flatmates, from Logic Problems, Issue 10, page 35.
Six people live in a three-storey block of studio flats laid out as in the plan. From the clues given, work out the name and situation of the resident of each flat.
Flat 5 Flat 3 Flat 1
Flat 6 Flat 4 Flat 2
1. Ivor and the photographer live on the same floor.
2. Edwinalivesimmediatelyabovethemedicalstudent.
3. Patrick, who is studying law, lives immediately above Ivor, and opposite the
air hostess.
4. Flat4isthehomeofthestoredetective.
5. DorislivesinFlat2.
6. RodneyandRosemaryare2oftheresidentsintheblockofflats.
7. Oneoftheresidentsisaclerk.
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 16
Logic Puzzles
Residents: Doris, Edwina, Ivor, Patrick, Rodney, Rosemary.
Professions: air hostess, clerk, law student, medical student, photographer, store detective.
male(ivor). male(patrick). male(rodney).
female(doris). female(edwina). female(rosemary).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 17
Logic Puzzle Solution
flatmates([L,R]) :-
L = [[5,_,_], [3,_,_], [1,_,_]], R = [[6,_,_], [4,_,_], [2,_,_]],
opposite([_,ivor,_], [_,_,photographer], L, R),
member(C1, [L,R]),
nextto([_,edwina,_], [_,_,medical_student], C1),
member(C2, [L,R]), nextto([N1,patrick,law_student], [_,ivor,_], C2), opposite([N1,_,_], [_,H,air_hostess], L, R), female(H),
member([4,_,store_detective], R), member([2,doris,_], R),
append(L, R, A), member([_,rodney,_], A), member([_,rosemary,_], A),
member([_,_,clerk], A).
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog III: Problem Solving 18
Logic Puzzle Solution
nextto(X, Y, [X, Y|_]). nextto(X, Y, [_|R]) :-
nextto(X, Y, R).
opposite(X, Y, [X|_], [Y|_]). opposite(X, Y, [Y|_], [X|_]). opposite(X, Y, [_|R1], [_|R2]) :-
opposite(X, Y, R1, R2).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019