How does this n-queens Prolog solution work?

Question

I am trying to understand how this n-queens Prolog solution from N-Queens Problem‍​..How far can we go? works (there were no comments on the original page). I have tried to add comments where I could understand something:

generate([],_).          % A LIST BEING GENERATED
generate([H|T],N) :-
   H in 1..N ,           % NOT CLEAR IF IT INCLUDES ALL COMBINATIONS OR PERMUTATIONS
   generate(T,N).

lenlist(L,N) :- 
   lenlist(L,0,N).

lenlist([],N,N).
lenlist([_|T],P,N) :-
   P1 is P+1,
   lenlist(T,P1,N).

queens(N,L) :-           % MAIN FN: SEND NUMBER OF QUEENS AND GET ANSWER LIST OF LISTS
   generate(L,N),lenlist(L,N),     % GENERATE LIST BASED ON N OF ALL COMBINATIONS
   safe(L),              % CHECK WHICH ONES ARE SAFE (NON-ATTACKING)
   !,
   labeling([ffc],L).    % CHOOSE CORRECT ONES (WHY NEEDED IF ALREADY FOUND SAFE?)

notattack(X,Xs) :-       % FNS TO FIND QUEENS NOT ATTACKING
   notattack(X,Xs,1).

notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
   X #\= Y,
   X #\= Y - N,
   X #\= Y + N,
   N1 is N + 1,
   notattack(X,Ys,N1).

safe([]).                % RECURSIVE FN TO FIND LISTS WITH NON-ATTACKING QUEENS
safe([F|T]) :-
   notattack(F,T),
   safe(T).

I am far from clear how is the initial list being generated. Is it an all permutation list or only a random list? Moreover, why both safe and labeling functions are needed? Thanks for your help in advance.

Answer 1

Your assumption:

safe(L),    % check which ones are safe (non-attacking)

(lowercase) is wrong: safe(L) does not check whether the two queens are attacking: it will add constraints such that the queens will not attack during (and thus after) the labeling.

Safe is a recursive method that will, for a list [A, B, C] add the constraints:

A #\= B,
A #\= B - 1,
A #\= B + 1,
A #\= C,
A #\= C - 2,
A #\= C + 2,
B #\= C,
B #\= C - 1,
B #\= C + 1.

These constraints are not enforced immediately in the sense that these assign values to A, B and C: these constraints are added and from the moment the domains of the variables is modified, the constraints will aim to reduce the domains of the other variables involved as well.

For instance in case the constraint is A #\= B and both A in 1..3 and B in 1..3, if labeling/2 will assign A = 1, then the constraint will fire, and reduce the domain of B to B in 2..3. Since it can no longer have value 1.

After the safe(L), we thus have added all constraints to the constraint store, and then labeling/2 can begin to search for the solution.