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.

Safe does not labels them, it simply adds constraints to the problem. — Willem Van Onsem, Sep 11 '17 at 16:47
Of interest: [Complexity of n-Queens Completion](http://jair.org/media/5512/live-5512-10126-jair.pdf) — Guy Coder, Sep 11 '17 at 16:49
Of interest: [one million dollar prize](http://www.sciencealert.com/if-you-like-chess-and-free-money-we-have-some-really-really-good-news) — Guy Coder, Sep 11 '17 at 17:00

score 3 · Accepted Answer · answered Sep 11 '17 at 17:13

3

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.

answered Sep 11 '17 at 17:13

Willem Van Onsem

443,496
30
428
555

Apparently, the `notattack` is adding constraints to each queen pair. What is `generate` generating? – rnso Sep 11 '17 at 17:27
@rnso: `generate/2` generates a list of `N` variables that are each in the domain `1..N`. But no constraints *between* the queens. – Willem Van Onsem Sep 11 '17 at 17:27
Why this `generate` and `lenlist` part not there in other solution? Or is it same as `length(Qs, N), Qs ins 1..N,` part of other solution? – rnso Sep 11 '17 at 17:34
@rmso: `generate/2` generates lists with variables `1..N` for *all* possible lengths (first an empty list, then a one-element list, etc.). Whereas `lenlist/2` checks if the list has the correct size. This implementation has some downsides because of that. – Willem Van Onsem Sep 11 '17 at 19:08

How does this n-queens Prolog solution work?

1 Answers1