I have read other similar questions and answers on this site, but can't seem to find the answer to my particular problem. I am trying to encode a maze in Prolog. From region 0, you can move freely to regions 1 or region 3. From region 3, you can move freely to region 0, region 4, or region 5, etc. I want to find the all paths of length 7 from the beginning to the end (from 0 to 14). I have encoded the problem in the following manner in SWI-Prolog:
region(0).
region(1).
region(2).
region(3).
region(4).
region(5).
region(6).
region(7).
region(8).
region(9).
region(10).
region(11).
region(12).
region(13).
region(14).
region(15).
connection(0,1). %connection exists between these two regions
connection(0,3).
connection(1,2).
connection(1,8).
connection(1,7).
connection(3,4).
connection(3,5).
connection(7,9).
connection(7,5).
connection(7,8).
connection(5,6).
connection(8,10).
connection(8,11).
connection(11,12).
connection(11,13).
connection(13,15).
connection(13,14).
double_link(X,Y) :-
region(X),
region(Y),
( connection(X,Y) | connection(Y,X) ). %can go from region X to region Y, and vice versa
path(X,Y) :-
double_link(X,Y).
path(X,Y) :-
double_link(X,Z),
path(Z,Y).
When I execute path(14,0). I get true. However, when I execute path(0,14)., I run out of local stack space. I don't know how that can be. Thanks for any help!
The problem arises because you can go in circles in the maze. E.g. in your maze you have the connections 0 - 1 - 7 - 5 - 3 - 0. You have not taken any measures to ensure that the search does not follow those circles blindly.
A usual approach would be to add an argument to your path predicate that contains the already visited regions (initially empty). Then you have to ensure when you go to a new location X that X is not in that list (e.g. with nonmember(X,Visited)).