Trying to count steps through recursion?

Question

This is a cube, the edges of which are directional; It can only go left to right, back to front and top to bottom.

edge(a,b).
edge(a,c).
edge(a,e).
edge(b,d).
edge(b,f).
edge(c,d).
edge(c,g).
edge(d,h).
edge(e,f).
edge(e,g).
edge(f,h).
edge(g,h).

With the method below we can check if we can go from A-H for example: cango(A,H).

move(X,Y):- edge(X,Y).
move(X,Y):- edge(X,Z), move(Z,Y).

With move2, I'm trying to impalement counting of steps required.

move2(X,Y,N):- N is N+1, edge(X,Y).
move2(X,Y,N):- N is N+1, edge(X,Z), move2(Z,Y,N).

How would I implement this?

Answer 1

arithmetic evaluation is carried out as usual in Prolog, but assignment doesn't work as usual. Then you need to introduce a new variable to increment value:

move2(X,Y,N,T):- T is N+1, edge(X,Y).
move2(X,Y,N,T):- M is N+1, edge(X,Z), move2(Z,Y,M,T).

and initialize N to 0 at first call. Such added variables (T in our case) are often called accumulators.

Answer 2

(is)/2 is very sensitive to instantiations in its second argument. That means that you cannot use it in an entirely relational manner. You can ask X is 1+1., you can even ask 2 is 1+1. but you cannot ask: 2 is X+1.

So when you are programming with predicates like (is)/2, you have to imagine what modes a predicate will be used with. Such considerations easily lead to errors, in particular, if you just started. But don't worry, also more proficient programmers still fall prey to such problems.

There is a clean alternative in several Prolog systems: In SICStus, YAP, SWI there is a library(clpfd) which permits you to express relations between integers. Usually this library is used for constraint programming, but you can also use it as a safe and clean replacement for (is)/2 on the integers. Even more so, this library is often very efficiently compiled such that the resulting code is comparable in speed to (is)/2.

?- use_module(library(clpfd)).
true.

?- X #= 1+1.
X = 2.

?- 2 #= 1+1.
true.

?- 2 #= X+1.
X = 1.

So now back to your program, you can simply write:

move2(X,Y,1):- edge(X,Y).
move2(X,Y,N0):- N0 #>= 1, N0 #= N1+1, edge(X,Z), move2(Z,Y,N1).

You get now all distances as required.

But there is more to it ...

To make sure that move2/3 actually terminates, try:

?- move2(A, B, N), false.
false.

Now we can be sure that move2/3 always terminates. Always? Assume you have added a further edge:

edge(f, f).

Now above query loops. But still you can use your program to your advantage! Determine the number of nodes:

?- setof(C,A^B^(edge(A,B),member(C,[A,B])),Cs), length(Cs, N).
Cs = [a, b, c, d, e, f, g, h],
N = 8.

So the longest path will take just 7 steps!

Now you can ask the query again, but now by constraining N to a value less than or equal to7:

?- 7 #>= N, move2(A,B, N), false.
false.

With this additional constraint, you have again a terminating definition! No more loops.

Answer 3

move2(X,Y,1):- edge(X,Y), ! .
move2(X,Y,NN):- edge(X,Z), move2(Z,Y,N), NN is N+1 .