title: Prolog transitive closure: maze pathfinder
body: <p>I'm interested in implementing a simple Prolog program that performs path finding queries on maze structures.</p>
  
  <pre><code>/* i_ -&gt; 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).
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>I modified <code>path</code> to include an additional requirement of <code>legal</code>, which serves as an accumulator:</p>
  
  <pre><code>/* path --&gt; 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]).
  </code></pre>
  
  <p>However, I'm now facing an issue with the var <code>Z</code> as a 'singleton'.</p>
  
  <p>Any suggestions as to how I can properly implement a accumulator so as to avoid excessive stack calls?</p>