prolog - 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

Let us first look at the top predicate. Here we solve the N×N queens problem by calling queens(N,Qs). The first call in the body length(Qs, N) constructs a list of variables with length N. Next it calls place_queens/4 with place_queens(N, Qs, _, _). It thus passes two free variables to the place_queens/4. Later we will, by unfication, construct a list.

The place_queens/4 first is called recursively until we hit zero for I, if we for example "unfold" the program for N = 4, we get:

place_queens(4, [Q1,Q2,Q3,Q4], UT, [D1,D2,D3,D4|DT]) :-
    place_queens(3, [Q1,Q2,Q3,Q4], [U4|UT], [D2,D3,D4|DT]) :-
        place_queens(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D3,D4|DT]) :-
            place_queens(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], [D4|DT]) :-
                place_queens(0, [Q1,Q2,Q3,Q4], [U1,U2,U3,U4|UT], DT),
                %% ---
                place_queen(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], DT),
            place_queen(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D4|DT]),
        place_queen(3, [Q1,Q2,Q3,Q4], [U4|UT], [D3,D4|DT]),
    place_queen(4, [Q1,Q2,Q3,Q4], UT, [D2,D3,D4|DT]).

(the above is not a Prolog code, it is an illustration to show the call structure.)

The place_queens thus does two things:

1. it "unfolds" a list of ups [U1, U2, U3, U4|_] and downs [D1, D2, D3, D4|_]; and
2. it calls place_queen with a specific value, and certain parts of the ups and downs list.

The task of the place_queen is to fill in the column I somewhere in the list. It always gets the entire list of queen positions [Q1, Q2, Q3, Q4] and parts of the ups and downs list. These ups and downs represent diagonals moving in the up and down direction.

In case we fill in a value for a given queen position, we also mark that value for the given ups and downs list, and thus "claim" these diagonals for that queen. If we do the bookkeeping properly that is sufficient, since if another queen wants to take a place that is on a diagonal that is already claimed, it aims to attach that value to the corresponding diagonal, but it will fail, since its value differs from the already assigned value.

Let us demonstrate that with an example. When we call the first place_queen(1, [Q1, Q2, Q3, Q4], [U2, U3, U4|_], _), we can assign that tho the first position, this is the basecase, so this results in the fact that:

place_queen(1,[Q1,Q2,Q3,Q4],[U2,U3,U4|_], _D) :-
    Q1 = 1,
    U2 = 1,
    _D = [1|_].

so that means that now our [Q1, Q2, Q3, Q4] looks like [1, Q2, Q3, Q4], for the up diagonals it looks like [U1, U2, U3, U4|_] = [U1, 1, U3, U4|_] and for [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1|_].

Now we aim to assign the next place_queen(2, [1,Q2,Q3,Q4],[U3,U4|_], [D4, 1|_]). We know we can not assign that value to the first item of the Q list, since that value is occupied by 1, and thus that would mean that two queens have the same column and attack each other, so that will not work.

We thus perform recursion, and hereby we pop both the up and down list, so:

place_queen(2, [1,Q2,Q3,Q4], [U3,U4|UT], [D4, 1|DT]) :-
    place_queen(2, [Q2,Q3,Q4], [U4|UT], [1|DT]).

So now we aim to put the queen for row two on the second column of the board, but there is again a problem: the diagonal of that square is already claimed, again by queen 1, we can derive that form the fact that down has [1|_]. So again we have to perform recursion, like:

place_queen(2, [1,Q2,Q3,Q4], [U4|UT], [1|DT]) :-
    place_queen(2, [Q3,Q4], UT, DT).

Here we can safely place the queen, here, none of the lists are blocking. So when we do that, the lists now look like [Q1, Q2, Q3, Q4] = [1, Q2, 2, Q4], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, 2|_] and [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, 2|_]. If we look at the board we have assigned, the diagonals indeed make sense:

 D5 D6 D7  D8
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   | Q |   |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

So as we can see the first queen claims D5 and U2, and the second queen claims D6 and U5.

Now we can place the third queen on the board, or at least we can try to do that, we thus make a call with place_queen(3,[1,Q2,2,Q4],[U4,2|_],[D3,D4,1,2|_]).

Here we will fail to place it at the first column (since it is occupied by queen 1), fail to put it on the second column (the up diagonal is claimed by queen 2), the third column (the column is occupied by queen 2 and the down diagonal is claimed by queen 1), and the last column (the down diagonal is claimed by queen 2). Eventually we run out of the Q list, so we will have to backtrack over the previous queen's assignment.

So now we continue with placing the second queen, the only option left, is to place it at the last column:

 D5 D6 D7  D8
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

In that case the [Q1, Q2, Q3, Q4] = [1, Q2, Q3, 2], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, U5, 2|_] and [D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, D6, 2|_]. So now the question is where to put the next queen (queen 3):

we can again assign the third queen, and we thus call the predicate now with place_queen(3,[1,Q2,Q3,2],[U4,U5,2|_],[D3,D4,1,D6,2|_]). We can not assign that queen to the first location, since queen 1 occupies that column, we thus recursively call it with place_queen(3,[Q2,Q3,2],[U5,2|_],[D4,1,D6,2|_]). Here there is no problem to put the queen, since the head of all three the lists is a free variable. We thus set Q2 = U5 = D4 = 3, and thus obtain the following board:

 D5 D6 D7  D8
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

So now our lists look like [Q1, Q2, Q3, Q4] = [1, 3, Q3, 2], [U1, U2, U3, U4|_] = [U1, 1, U3, U4, 3, 2|_] and [D1, D2, D3, D4|_] = [D1, D2, D3, 3, 1, D6, 2|_]. Now we can eventually assign the last queen to the board, we thus call the place_queen/4 with place_queen(4,[1,3,Q3,2],[3,2|_],[D2,D3,3,1,D6,2|DT]).. The first two places are rejected (occupied both by column and by up diagonal), so after two recursive calls, we end up with place_queen(4,[Q3,2],_,[3,1,D6,2|DT]), but that one is occupied by queen 3 (down diagonal), indeed, the situation looks like this:

 D5 D6 D7  D8
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

So again we found that this does not yield a sulution. Prolog will keep backtracking, and eventually will come up with the solution:

 D5 D6 D7  D8
  +---+---+---+---+
 /|   | Q |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /| Q |   |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

Then the lists look like Qs = [3, 1, 4, 2], U = [1, 3, _, 2, 4|_] and D = [_, _, 3, 4_, 1, 2|_].

So we can conclude that the values in the up and downlist are not relevant on itself, it is used to prevent to assign a different number (queen) on these diagonals.