Prolog Examples

EXAMPLE:

The above figure represents a maze in which we are asked "is there a route from point X to point Y?"

We start by defining the database of facts which describe the paths between points (squares in the above diagram):

path(a,b).
path(b,c).
path(c,d).
path(f,c).
path(b,e).
path(d,e).
path(e,f).

Now to define routes between points.

Firstly the simple case:

route(X,X).

Then the other case - each route from X to Y starts with a path from X to Z that is in the database, and then there is a route from Z to Y. Or put another way, a path exists from X to Y if there is a path from X to Z and a route from Z to Y.

That is:

route(X,Y) :- path(X,Z), route(Z,Y).

NOTE: This solution gets into problems when there are loops in the possible routes. The final solution involves keeping a list of squares traversed and making sure that a square is never revisited.


ADVANCED EXAMPLE:

Question 1: Is there a path which when traversed the numbers add up to 15?

Question 2 (Even more advanced): Is there a path for which there is a additive value greater than 15? What is that value?

Question 3 (REAL advanced): For each of the questions above print out the path sequence.

[TOC][Next]

CS1104 Main Page


Last updated 2001/04/06
© J.A.N. Lee, 2001.