Recursion in Prolog - Finding Path Between Cities

Question

I'm trying to work my way through the exercises at the bottom of this page and I find myself utterly confused on number 3.

We are given the following knowledge base of travel information:

byCar(auckland, hamilton). 
byCar(hamilton, raglan). 
byCar(valmont, saarbruecken). 
byCar(valmont, metz). 

byTrain(metz, frankfurt). 
byTrain(saarbruecken, frankfurt). 
byTrain(metz, paris). 
byTrain(saarbruecken, paris). 

byPlane(frankfurt, bangkok). 
byPlane(frankfurt, singapore). 
byPlane(paris, losAngeles). 
byPlane(bangkok, auckland). 
byPlane(singapore, auckland). 
byPlane(losAngeles, auckland).

It's simple to find out if it's possible to travel between two cities. I just did this:

connected(X, Y) :- byCar(X, Y); byTrain(X, Y); byPlane(X, Y).
travel(X, Y) :- connected(X, Y).
travel(X, Z) :- connected(Y, Z), travel(X, Y).

However, when I have to actually unify the path with a variable, I am utterly confused!

I wrote this:

connected(X, Y) :- byCar(X, Y); byTrain(X, Y); byPlane(X, Y).
connected(Y, Z, Out) :- connected(Y, Z).
travel(X, Y, Out) :- connected(X, Y).
travel(A, Z, Out) :- connected(Y, Z),travel(A, Y, connected(Y, Z, Out)).

And called travel(valmont, losAngeles,X).

There is a point during the trace where the correct path shows up, aside from the anonymous variable at the end:

travel(valmont, metz, connected(metz, paris, connected(paris, losAngeles, _17)))

but I don't actually know how to unify this with the variable X!

I can't really wrap my mind around this. Can anyone give me a hint just to push me in the right direction? Is there just a termination condition I'm missing or something?

Edit:

Now I have:

connected(X,Y) :- byCar(X,Y);byTrain(X,Y);byPlane(X,Y).

go(X,Y) :- connected(X,Y).

travel(X,Y,go(X,Y)) :- connected(X,Y).
travel(A,Z,Path) :- travel(Y,Z,Path),go(A,Y,Path).

go(A,Y,Path) :- travel(A,Y,Path).

but it gets stuck like this:

4    4  Exit: byPlane(paris,losAngeles) ? 
3    3  Exit: connected(paris,losAngeles) ? 
2    2  Exit: travel(paris,losAngeles,go(paris,losAngeles)) ? 
5    2  Call: go(metz,paris,go(paris,losAngeles)) ? 
6    3  Call: travel(metz,paris,go(paris,losAngeles)) ? 
7    4  Call: travel(_217,paris,go(paris,losAngeles)) ? 
8    5  Call: travel(_242,paris,go(paris,losAngeles)) ? 
9    6  Call: travel(_267,paris,go(paris,losAngeles)) ? 
10    7  Call: travel(_292,paris,go(paris,losAngeles)) ? 

I've played around with it, but I can't get it to build the whole go(a,b,go(b,c)) etc...

Answer 1

I'll give you the base case of the recursion:

travel(X, Y, go(X, Y)) :- connected(X, Y).

The recursive case looks extremely similar, except that the go/3 term you're building must have locations as its first two arguments, and a path (another go/2 or go/3 term) as its second.

Answer 2

I had this explained to me by aBathologist the following way:

Your objective is to get X = go(valmont,metz,go(metz,paris,go(paris,losAngeles))) in response to the query travel(valmont,losAngeles,X).

To solve this problem, your travel/3 predicate needs to have a From, To, and Path, but it must end with a simple go(From, To) without the Path. The simple go(From, To) is your base condition of travel/3, so:

travel(X, Y, go(X, Y)) :- connected(X, Y).

This is exactly as larsmans states.

Now, you need to create your recursive travel/3 predicate:

travel(X, Y, go(X, Z, Path)) :-
 connected(X, Z),
 travel(Z, Y, Path).

Your go/2 predicate is redundant and a little confusing given the travel/3 predicate has something that looks like a go predicate. By removing the go/2 predicate, the code is a little easier to read and understand.