Search code examples
loopsprologmaze

Prolog maze stop looping


I've managed to piece together a script which goes through all of links and display them back to me however I can't seem to work out why with the one of the links the entire script loops to infinity. If you remove the link below the program will work;

link(f,c).

Below is the code to the complete script;

link(a,b).
link(a,b).
link(b,c).
link(c,d).
link(f,c).
link(b,e).
link(d,e).
link(e,f).

path(X,Y,[X,Y]):-link(X,Y). 
path(X,Y,[X|R]):-link(X,Z),path(Z,Y,R).
route(X,Y,T):-find_route(X,Y,[],T).
find_route(X,Y,D,[Z|T]):-path(X,Y,Z),not(member(Z,D)), 
find_route(X,Y,[Z|D],T). 
find_route(_,_,_,[]).

It seems it currently matches the values in the array with links values then compares the paths from a to f, after that it checks the values which have passed through and displays them on the console(This is without link(f,c).) If anyone knows where I've gone through please let me know.

Thanks


Solution

  • The link (f,c) is effectively closing the directed loop c->d->e->f->c. So any backtracking on path(X,Y,Z) with X and Y belonging to this loop will produce longer and longer paths. So You should add a check to your path rule to avoid already visited nodes.