DarkyTheOdd
DarkyTheOdd

Reputation: 128

Prolog out of local stack space/ infinite recursion

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!

Upvotes: 2

Views: 509

Answers (2)

false
false

Reputation: 10102

You said:

When I execute path(14,0). I get true.

That is half of the truth! Oh, even less than that! In fact you get true not once but many times!

?- path(14,0).
   true
;  true
;  true
;  true
;  true
;  true
;  ... .

There is a simple way to avoid typing ; or SPACE all the time. Simply use the goal false.

?- path(14,0), false
   loops.

And now, you can also add such false-goals into your program. In this manner you are ruling out parts of the program ; and if the remaining part still loops, you know that there must be a problem there. This is what I got:

region(0) :- false.
% ...
region(12) :- false.
region(13).
region(14).
region(15) :- false.

connection(0,1) :- false.
% ...
connection(13,15) :- false.
connection(13,14).

double_link(X,Y) :-
   region(X),
   region(Y),
   ( connection(X,Y) ; connection(Y,X) ).

path(X,Y) :- false,
   double_link(X,Y).
path(X,Y) :-
   double_link(X,Z),
   path(Z,Y), false.

So in this remaining part that loop has to be addressed. It should be now self-explanatory, isn't it?

Upvotes: 4

danielp
danielp

Reputation: 1187

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)).

Upvotes: 2

Related Questions