Unexpected Behavior of Prolog program

Question

I have written a prolog program to search for a path in an un-directed graph (or maze).

pway(a, b,10).
pway(b, e,10).
pway(b, c,10).
pway(d, e,10).
pway(c, d,10).
pway(e, f,10).
pway(g, e,10).

solve(X,X,T,N) :-
    write(T), N is 0. % do nothing
solve(X,Y,T,N) :-
    pway(X, Z,C),
    not(member(Z, T)),
    solve(Z, Y, [Z|T],M),
    N is M+C. % There is a pway from X to Z, new list has z as head.
solve(X,Y,T,N) :-
    pway(Z, X,C),
    not(member(Z, T)),
    solve(Z, Y, [Z|T],M),N is M+C. % same, just takes care of non-directedness

I intend to use this program for queries like:

?- solve(a,f,P,N).

i.e. give me the paths P from a to f with their costs.

But this does not work as intended. When I enter (P is intended to be a list),

?- solve(e,b,P,N).
false.

I get false. (Why ??)

But, when I enter:

?- solve(e,b,[],N).
[b,e,f]
N = 30 ;
[b,c,d,e,f]
N = 50 ;
[b]
N = 10 ;
[b,e,d]
N = 30 ;
[b,c,d]
N = 30 ;
[b,e,g]
N = 30 ;
[b,c,d,e,g]
N = 50 ;
false.

I get the results. Actually, I never wanted to use write commands in the prolog program itself, I should have got the same results just by entering the first query (which returned false). I can't identify the error.

Any help is appreciated. Thanks.

But this does not work as intended. What is intended? What do you get (in simple words - an invalid path? A longer than expected path?) ... ? — amit
@amit I mean Intended output (or the correct result of the query) The output should have been the list with the paths's nodes rather than false. — Novak007
Consider using the \+/1 standard predicate/operator for negation (as failure) instead of the old, deprecated, not standard not/1 predicate. E.g. write \+ member(Z, T) instead of not(member(Z, T)). — Paulo Moura

findall findall · Accepted Answer · 2015-02-11T10:13:05

This is because the #3 argument is not path between two nodes in #1 and #2, as you expected. If you pass a variable in the #3, the goal not(member(Z, T)) always fails, so solve/3 fails as well.

Judging from what you said, what you want to do is probably something like this.

solve(X,Y,T,N) :- solve(X,Y,[],N,T).

solve(X,X,T,0,T).

solve(X,Y,T,N,O) :-
    pway(X, Z,C),
    \+ member(Z, T),
    solve(Z, Y, [Z|T],M,O),
    N is M+C.

solve(X,Y,T,N,O) :-
    pway(Z, X,C),
    \+ member(Z, T),
    solve(Z, Y, [Z|T],M,O),N is M+C.

Unexpected Behavior of Prolog program

1 Answers