CODEWITHSUNDEEP
prolog
John Gann
John Gann

Reputation: 605

PROLOG local stack overflow

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

Upvotes: 1

Views: 968

Answers (1)

CapelliC
CapelliC

Reputation: 60034

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

Upvotes: 1

Related Questions