I'm interested in implementing a simple Prolog program that performs path finding queries on maze structures.
/* i_ -> intersections */
i_(c,b). /* horizontal adjacencies */
i_(g,h).
i_(h,i).
i_(i,g).
i_(a,d). /* vertical adjacencies */
i_(d,g).
i_(c,f).
i_(f,i).
/* symmetric interface */
i(X,Y) :- i_(X,Y);i_(Y,X).
/* path, the rule in question*/
path(X,Y) :- i(X,Y) ; i(X,Z), path(Z,Y).
Bug: My Prolog interpreter (SWI) is thrown into a state of infinite recursion when path is used with input nodes >= 5 steps away. However, the rule works fine with fewer than 5 nodes step in path. Curiously,omitting the rule of symmetry (simply declaring each adjacency, backwards and forwards), reduces the call limit of path to fewer than 3 nodes difference. Overriding the default stack allocation again increases the span of path before stack overflow.
Obviously, an accumulator is in order. I suspect that my program crashes at run time because the interpreter continues to revisit nodes already traversed in the path.
I modified path to include an additional requirement of legal, which serves as an accumulator:
/* path --> recursive path check */
legal(Z,[]).
legal(Z,[H|T]):- Z\==H, legal(Z,T).
path(X,Y,T) :- i(X,Y) ; i(X,Z), legal(Z,T), path(Z,Y,[Z|T]).
However, I'm now facing an issue with the var Z as a 'singleton'.
Any suggestions as to how I can properly implement a accumulator so as to avoid excessive stack calls?
