PROLOG local stack overflow

Question

The following code is giving me a fatal local stack overflow error (after all solutions are found, instead of "no"), and I don't understand why. I'm pretty sure that it has something to do with the range predicate, since if I replace it with a list, I don't have the issue, but I don't understand how it's causing an overflow.

nqueens(N,X) :-
  pattern(N,X),range(N,Yrange),legal(Yrange,X).

nocheck(_, []).
nocheck(X/Y, [X1/Y1 | Rest]) :-
  Y =\= Y1,
  abs(Y1-Y) =\= abs(X1-X),
  nocheck(X/Y, Rest).

legal(_,[]).
legal(Yrange,[X/Y | Rest]) :-
  legal(Yrange,Rest),
  member(Y,Yrange),
  nocheck(X/Y, Rest).

pattern(1,[1/_]).
pattern(N,[N/_|T]) :- N1 is N-1,pattern(N1,T).

range(1,[1]).
range(N,[N|T]) :- N1 is N-1,range(N1,T).

It generally means that your end condition is never met, and that you should use the trace command, followed by your actual query, to step through what is actually happening. You should add what you're actually trying to achieve with your program to the question, as Prolog is goal-oriented and without specifying what you want to achieve, we can only guess. — G_V
You need a N > 1 condition in the second clause of your range/2 predicate. — lurker

CapelliC CapelliC · Accepted Answer · 2018-03-15T07:27:34

When N in range/2 becomes 1, the following clause should not be left for eventual further processing (that will happen on backtracking), since it will become negative and the recursion will not stop anymore. You can either test for positiveness in the second clause

range(N,[N|T]) :- N>0,N1 is N-1,range(N1,T).

or - I think - just cut after the first one

range(1,[1]) :- !.

Another possibility would be to make the predicate deterministic at call point:

nqueens(N,X) :-
  pattern(N,X),once(range(N,Yrange)),legal(Yrange,X).

PROLOG local stack overflow

1 Answers