Hints to understand splendid program to solve Queens

Question

In Art of Prolog of Sterling & Shapiro, exercise Section 14.1 (v):

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_,_).

place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs),
    place_queen(I,Qs,Ups,Downs).

place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
    place_queen(Q,Qs,Ups,Downs).

It is a splendid program, in 11 lines, which quickly solves the problem of positioning queens on a chessboard. It's magical: there is only a counter, recursion, and lists that get longer and shorter. I, even with the help of trace, don't understand it. Can someone explain it to me? How do you get to write such a program? What is the logical / mental process that leads to derive this program from, for example, this other (good standard solution):

queens(N,Qs) :-
    numlist(1,N,Ns), 
    queens(Ns,[ ],Qs).

queens(UnplacedQs,SafeQs,Qs) :-
    select(Q,UnplacedQs,UnplacedQs1),
    \+ attack(Q,SafeQs),
    queens(UnplacedQs1,[Q|SafeQs] ,Qs).
queens([ ],Qs,Qs).

attack(X,Xs) :-
    attack(X,1,Xs).

attack(X,N,[Y|_]) :-
    X is Y+N ; X is Y-N.
attack(X,N,[_|Ys]) :-
    N1 is N+1,
    attack(X,N1,Ys).

Answer 1

Having understood the program thanks to previous good answers, I try to give a more declarative explanation.
The author of the program is Thom Frühwirth (thanks to Jschimpf for the information).
I quote an extract from his message posted on comp.lang.prolog:

Observing that no two queens can be positioned on the same row, column or diagonals, we place only one queen on each row. Hence we can identify the queen by its row-number. Now imagine that the chess-board is divided into three layers, one that deals with attacks on columns and two for the diagonals going up and down respectively. We indicate that a field is attacked by a queen by putting the number of the queen there. Now we solve the problem by looking at one row at a time, placing one queen on the column and the two diagonal-layers. For the next row/queen we use the same column layer, to get the new up-diagonals we have to move the layer one field up, for the down-diagonals we move the layer one field down.

His program:

% -------- Meaning of Variables ------
% N, M  ... Size of the board
% I, J  ... Number of the row current queen is on
% Qs, L ... List of length N used to represent the solution
% Cs ... Column as a list of fields of length N
% Us ... Up-Diagonal as an open list of fields
% Ds ... Down-Diagonal as an open list of fields


queens(N,Qs):- gen_list(N,Qs), place_queens(N,Qs,_,_).

gen_list(0,[]).
gen_list(N,[_|L]):-
        N>0, M is N-1,
        gen_list(M,L).

place_queens(0,_,_,_).
place_queens(I,Cs,Us,[_|Ds]):-
        I>0, J is I-1,
        place_queens(J,Cs,[_|Us],Ds),
        place_queen(I,Cs,Us,Ds).

% place_queen(Queen,Column,Updiagonal,Downdiagonal) places a single queen
place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
                place_queen(I,Cs,Us,Ds).

Let's go back to the question. Let's make the problem easier. Let's just consider the rows, the columns and the up-diagonals.

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_).

place_queens(0,_,_).    
place_queens(I,Qs,Ups) :-
    I > 0,
    I1 is I-1,
    place_queens(I1,Qs,[_|Ups]),
    place_queen(I,Qs,Ups).

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

?- queens(3,L).
L = [1, 2, 3];        
L = [3, 1, 2];       % row 3/col 1 -- row 1/col 2 -- row 2/col 3
L = [2, 3, 1];
false

Chessboard of side 3 with up-diagonals:

    C1  C2  C3
    |   |   |     Row
  +---+---+---+
U1| / | / | / |-- 1
  +---+---+---+
U2| / | / | / |-- 2
  +---+---+---+
U3| / | / | / |-- 3
  +---+---+---+
   U3  U4  U5

and the predicate that relates rows/queens, lists of columns/queens and lists of up-diagonals/queens:

row_col_ups(1, [ 1,C2,C3], [ 1,U2,U3,U4,U5]). % row 1
row_col_ups(1, [C1, 1,C3], [U1, 1,U3,U4,U5]).
row_col_ups(1, [C1,C2, 1], [U1,U2, 1,U4,U5]).

row_col_ups(2, [ 2,C2,C3], [U1, 2,U3,U4,U5]). % row 2
row_col_ups(2, [C1, 2,C3], [U1,U2, 2,U4,U5]).
row_col_ups(2, [C1,C2, 2], [U1,U2,U3, 2,U5]).

row_col_ups(3, [ 3,C2,C3], [U1,U2, 3,U4,U5]). % row 3
row_col_ups(3, [C1, 3,C3], [U1,U2,U3, 3,U5]).
row_col_ups(3, [C1,C2, 3], [U1,U2,U3,U4, 3]).

Consider the place_queen/3 predicate:

% place_queen(Q,Cols,Ups)
% Q    -> queen/row
% Cols -> list of colunms/queens
% Ups  -> open list of up-diagonals/queens

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

It has the same structure as member/2:

member(X,[X|_]).
member(X,[_|L]):-
    member(X,L).

?- member(3,[1,2,3]).
true.
?- member(X,[1,2]).
X = 1;
X = 2.

But it is used in an unusual way:

?- L=[1,2,X,4], member(3,L).
L = [1, 2, 3, 4],
X = 3

?- member(3,L).
L = [3|_1388];
L = [_1178, 3|_1186];
L = [_1178, _1184, 3|_1192];

So, place_queen looks for an empty square, if it exists, where to put the Queen.

?- Col=[C1,C2,C3], place_queen(3,Col,UPS).
Col = [3, C2, C3],
UPS = [3|_]

?- Col=[C1,C2,C3], place_queen(1,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2).
Col = [3, C2, 2],
UPS = [3, 2|_],
UPS2 = [U2, 3, 2|_]

?- Col=[C1,C2,C3], place_queen(3,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2), UPS3=[U1|UPS2], place_queen(1,Col,UPS3).
Col = [3, 1, 2],
UPS = [3, 2|_],
UPS2 = [1, 3, 2|_],
UPS3 = [U1, 1, 3, 2|_]

The diagonals (up and down) are represented by open-list, that is, lists to which elements can be added, if necessary, in the queue. place_queens handles them and the relationship between rows and diagonals.

place_queens(0,_Qs,_Ups,_Downs). % usually pred(0,[],[],[]) for closed list
                                 % but with open-lists we have the variables.

place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs), %  in next row/queen 
    place_queen(I,Qs,Ups,Downs).        %  for the up-diagonals we move the layer
                                        %  one field up.
                                        %  for the down-diagonals we move the layer
                                        %  one field down.

---

P.S. Predicate that relates rows/queens, lists of columns/queens and lists of down-diagonals/queens in chessboard of side 3:

row_col_downs(1, [ 1,C2,C3], [D1,D2, 1,D4,D5]).
row_col_downs(1, [C1, 1,C3], [D1,D2,D3, 1,D5]).
row_col_downs(1, [C1,C2, 1], [D1,D2,D3,D4, 1]).

row_col_downs(2, [ 2,C2,C3], [D1, 2,D3,D4,D5]).
row_col_downs(2, [C1, 2,C3], [D1,D2, 2,D4,D5]).
row_col_downs(2, [C1,C2, 3], [D1,D2,D3, 2,D5]).

row_col_downs(3, [ 3,C2,C3], [ 3,D2,D3,D4,D5]).
row_col_downs(3, [C1, 3,C3], [D1, 3,D3,D4,D5]).
row_col_downs(3, [C1,C2, 3], [D1,D2, 3,D4,D5]).

P.P.S.Thom Frühwirth gives two other versions of the program, one of which is in pure Prolog:

% Pure version with successor function

queensp(N,Qs):- gen_listp(N,Qs), place_queensp(N,Qs,_,_).

gen_listp(0,[]).
gen_listp(s(N),[_|L]):-
        gen_listp(N,L).

place_queensp(0,_,_,_).
place_queensp(s(I),Cs,Us,[_|Ds]):-
        place_queensp(I,Cs,[_|Us],Ds),
        place_queen(s(I),Cs,Us,Ds).

place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
        place_queen(I,Cs,Us,Ds).

?- queensp(Q,L).
L = [],
Q = 0 ;
L = [s(0)],
Q = s(0) ;
L = [s(s(s(0))), s(0), s(s(s(s(0)))), s(s(0))],
Q = s(s(s(s(0))))