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

Last updated 2001/04/06

© J.A.N. Lee, 2001.