CODEWITHSUNDEEP
prolog
nofar mishraki
nofar mishraki

Reputation: 618

prolog - Error 1, Backtrack Stack Full

im trying to write a program in prolog that determine if there is a way from place to place. these are the relations:

road(ny,florida).
road(washington,florida).
road(washington,texas).
road(vegas,california).

I want to write: there_is_way(X,Y) that determine if there is a way or not. for example:

?- road(florida,ny).
no
?-there_is_way(florida,ny).
yes

This is my code:

there_is_way(X,Y):- road(X,Y);
                        road(Y,X);
                        road(X,Z),road(Z,Y),X\=Y;
                        road(X,Z),road(Y,Z),X\=Y;
                        road(Z,X),road(Z,Y),X\=Y;
                        road(Z,X),road(Y,Z),X\=Y.
there_is_way(X,Y):-
                        road(Z,Y),there_is_way(X,Z).
there_is_way(X,Y):-
                        road(Y,Z),there_is_way(X,Z).

but unfortunately I get "Error 1, Backtrack Stack Full".

someone?

thank you

Upvotes: 2

Views: 262

Answers (2)

false
false

Reputation: 10102

First, we need a symmetric definition:

:- meta_predicate symm(2, ?,  ?).

symm(P_2, A, B) :-
   call(P_2, A, B).
symm(P_2, A, B) :-
   call(P_2, B, A).

Now, using closure0/3

there_is_way(A, B) :-
   closure0(symm(road), A, B).

Upvotes: 2

user27815
user27815

Reputation: 4797

If you are treating the road/2 as a directed edge, then you can simply have:

road(ny,florida).
road(washington,florida).
road(washington,texas).
road(vegas,california).

there_is_way(X,Y):- road(X,Y).
there_is_way(X,Y):- road(X,Z),there_is_way(Z,Y).

If however you have a loop in your graph, either because of the directions or you assume that road/2 is an undirected edge (and correspondingly implement this) then you need to keep track of where you have been while route finding. Otherwise you will get into an infinite loop. Remember prolog searches depth first by default so you need to make a check that when adding an item to a route it is not already there, otherwise prolog will find the same route over and over..

See chapter 5 of this book: https://www.cs.bris.ac.uk/~flach/SL/SL.pdf for a complete discussion.

Upvotes: 1

Related Questions