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

Revis

This seems to be a program posted to comp.lang.prolog in 1991 by my former colleague Thom Frühwirth, see groups.google.com/d/msg/comp.lang.prolog/qiyibDALhTE/… for some extra explanation. – Sigh

I also don't fully understand what is happening in this program, but it does seem to have something to do with the fact that Ups and Downs get modified going into and coming out of recursive calls respectively. I think that has something to do with handling the diagonal attack of queens, but I'm not sure how. – Ac

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.

Fronnia

Wow, thank you for unpacking that! What a surprising program! – Ac

I borrowed your initial illustration and moved its pieces around to see what's what better. – Farreaching

Answer 2

The code in the first part of the question is what is explained here. The code is reposted here to ensure a reader doesn't mistakenly look at the wrong code.

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

This code as is most Prolog solutions to the N-Queens problem a generate and test. The code generates a possible solution and test it. However instead of generating all positions for one possible answer at once, the queen positions are set incrementally and changed upon a partial failure until a complete solution is found.

There is one written test in the code which is

place_queen(Q,[Q|_],[Q|_],[Q|_]).

To understand this requires understanding what the meaning of the arguments as related to this statement from here

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.

The first argument represents a queen identified by a positive integer and which is bound.

The second argument represents a column and is always a list the size of the board where each potion in the list represents one of the columns of the board. The code uses the variable Qs for but to me it makes more sense as Rs, meaning rows. So if there is any bound value in a position in the list that would be a queen attacking in that column.

The third and fourth arguments work in principal in the same way and take care of the diagonal attack for the queen. One is for the diagonals going up and one the diagonals going down. Since they are diagonals again they are represented as list but depending upon the potion of a queen on the board that is being checked, the size of the diagonal going up may be different than the size of the diagonal going down.

For example in the image below the white queen represents the position of a queen being checked and the black queens going diagonally up represent the up going diagonal list and the other queen represents the down going diagonal list.

Note: Images generated using Chess Diagram Setup

The going up diagonal is length of two while the going down diagonal is length of one.

What the test states is that if a queen given in the first argument can be unified with the column attack argument, the going up diagonal attack and the going down diagonal attack then accept the queen in that position for a partial answer or complete answer if the queen is in the last position of the list in the second argument.

So for the test

place_queen(Q,[Q|_],[Q|_],[Q|_]).

which is the same as this written for clarity and documentation

place_queen(Q,Rs,Ups,Downs) :-
  Rs = [R_1|_],
  Ups = [U_1|_],
  Downs = [D_1|_],
  Q = R_1, Q = U_1, Q = D_1

then if

Q is 1
R_1 is unbound
U_1 is unbound
D_1 is unbound

The test past and 1 is bound to the variables R_1, U_1, and D_1.

and an example of a test that fails

Q is 3
R_1 is 1
U_1 is unbound
D_1 is unbound

Now for a call that fails as a test because of no value in the list.

Q is 2
R_1 is []
U_1 is unbound
D_1 is unbound

The rest of the code just generates cases for testing.

The second argument can be seen being generated by running this variation of the code.

queens(N) :-
    length(Qs,N),
    format("N: ~w, Qs: ~w~n",[N,Qs]).

?- queens(4).
N: 4, Qs: [_6476,_6482,_6488,_6494]
true.

The diagonal arguments can be seen being generated by running this variation of the code.

queens(N) :-
    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),
    format('I1: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I1,Qs,Ups,Downs]).

?- queens(4).
I1: 0, Qs: [_6474,_6480,_6486,_6492], Ups: [_6528,_6516,_6504|_6506], Downs: _6536
I1: 1, Qs: [_6474,_6480,_6486,_6492], Ups: [_6516,_6504|_6506], Downs: [_6534|_6536]
I1: 2, Qs: [_6474,_6480,_6486,_6492], Ups: [_6504|_6506], Downs: [_6522,_6534|_6536]
I1: 3, Qs: [_6474,_6480,_6486,_6492], Ups: _6506, Downs: [_6510,_6522,_6534|_6536]
true ;
false.

This small part

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

just says that if the position for the next queen did not work for a row in the column, then pick another row. Note that the example of above change the variable name of the second argument from Qs to Rs to say that it is row that is being changed.

To make it easier to see the generate and test in action, modify the code as such

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),
    format('Generate 1 - I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]),
    place_queen(I,Qs,Ups,Downs),
    format('Result    -> I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]).

place_queen(Q,Rs,Ups,Downs) :-
    Rs = [R_1|_],
    Ups = [U_1|_],
    Downs = [D_1|_],
    format('Test        - Q : ~w, R_1: ~w, U_1: ~w, D_1: ~w~n',[Q,R_1,U_1,D_1]),
    (
        Rs = [Q|_],
        Ups = [Q|_],
        Downs = [Q|_]
    ->
        format('Test success~n')
    ;
        format('Test failure~n'),
        fail
    ).

place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
    format('Generate 2 - Q: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[Q,Qs,Ups,Downs]),
    place_queen(Q,Qs,Ups,Downs).

An example run up to the first solution.

?- queens(4,Qs).
Generate 1 - I: 1, Qs: [_6488,_6494,_6500,_6506], Ups: [_6542,_6530,_6518|_6520], Downs: _6550
Test        - Q : 1, Q_1: _6488, U_1: _6542, D_1: _6596
Test success
Result    -> I: 1, Qs: [1,_6494,_6500,_6506], Ups: [1,_6530,_6518|_6520], Downs: [1|_6598]
Generate 1 - I: 2, Qs: [1,_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: [_6548,1|_6598]
Test        - Q : 2, Q_1: 1, U_1: _6530, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [_6494,_6500,_6506], Ups: [_6518|_6520], Downs: [1|_6598]
Test        - Q : 2, Q_1: _6494, U_1: _6518, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: _6598
Test        - Q : 2, Q_1: _6500, U_1: _6746, D_1: _6752
Test success
Result    -> I: 2, Qs: [1,_6494,2,_6506], Ups: [_6530,_6518,2|_6748], Downs: [_6548,1,2|_6754]
Generate 1 - I: 3, Qs: [1,_6494,2,_6506], Ups: [_6518,2|_6748], Downs: [_6536,_6548,1,2|_6754]
Test        - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,2,_6506], Ups: [2|_6748], Downs: [_6548,1,2|_6754]
Test        - Q : 3, Q_1: _6494, U_1: 2, D_1: _6548
Test failure
Generate 2 - Q: 3, Qs: [2,_6506], Ups: _6748, Downs: [1,2|_6754]
Test        - Q : 3, Q_1: 2, U_1: _6902, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [_6506], Ups: _6898, Downs: [2|_6754]
Test        - Q : 3, Q_1: _6506, U_1: _6932, D_1: 2
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6928, Downs: _6754
Generate 2 - Q: 2, Qs: [_6506], Ups: _6742, Downs: _6748
Test        - Q : 2, Q_1: _6506, U_1: _6782, D_1: _6788
Test success
Result    -> I: 2, Qs: [1,_6494,_6500,2], Ups: [_6530,_6518,_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Generate 1 - I: 3, Qs: [1,_6494,_6500,2], Ups: [_6518,_6740,2|_6784], Downs: [_6536,_6548,1,_6746,2|_6790]
Test        - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,_6500,2], Ups: [_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Test        - Q : 3, Q_1: _6494, U_1: _6740, D_1: _6548
Test success
Result    -> I: 3, Qs: [1,3,_6500,2], Ups: [_6518,3,2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Generate 1 - I: 4, Qs: [1,3,_6500,2], Ups: [3,2|_6784], Downs: [_6524,_6536,3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: 1, U_1: 3, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [3,_6500,2], Ups: [2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: 3, U_1: 2, D_1: _6536
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6784, Downs: [3,1,_6746,2|_6790]
Test        - Q : 4, Q_1: _6500, U_1: _7070, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [2], Ups: _7066, Downs: [1,_6746,2|_6790]
Test        - Q : 4, Q_1: 2, U_1: _7100, D_1: 1
Test failure
Generate 2 - Q: 4, Qs: [], Ups: _7096, Downs: [_6746,2|_6790]
Generate 2 - Q: 3, Qs: [_6500,2], Ups: [2|_6784], Downs: [1,_6746,2|_6790]
Test        - Q : 3, Q_1: _6500, U_1: 2, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [2], Ups: _6784, Downs: [_6746,2|_6790]
Test        - Q : 3, Q_1: 2, U_1: _6962, D_1: _6746
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6958, Downs: [2|_6790]
Generate 2 - Q: 2, Qs: [], Ups: _6778, Downs: _6784
Generate 2 - Q: 1, Qs: [_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: _6586
Test        - Q : 1, Q_1: _6494, U_1: _6530, D_1: _6626
Test success
Result    -> I: 1, Qs: [_6488,1,_6500,_6506], Ups: [_6542,1,_6518|_6520], Downs: [_6584,1|_6628]
Generate 1 - I: 2, Qs: [_6488,1,_6500,_6506], Ups: [1,_6518|_6520], Downs: [_6548,_6584,1|_6628]
Test        - Q : 2, Q_1: _6488, U_1: 1, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [1,_6500,_6506], Ups: [_6518|_6520], Downs: [_6584,1|_6628]
Test        - Q : 2, Q_1: 1, U_1: _6518, D_1: _6584
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: [1|_6628]
Test        - Q : 2, Q_1: _6500, U_1: _6776, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6506], Ups: _6772, Downs: _6628
Test        - Q : 2, Q_1: _6506, U_1: _6806, D_1: _6812
Test success
Result    -> I: 2, Qs: [_6488,1,_6500,2], Ups: [1,_6518,_6770,2|_6808], Downs: [_6548,_6584,1,2|_6814]
Generate 1 - I: 3, Qs: [_6488,1,_6500,2], Ups: [_6518,_6770,2|_6808], Downs: [_6536,_6548,_6584,1,2|_6814]
Test        - Q : 3, Q_1: _6488, U_1: _6518, D_1: _6536
Test success
Result    -> I: 3, Qs: [3,1,_6500,2], Ups: [3,_6770,2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Generate 1 - I: 4, Qs: [3,1,_6500,2], Ups: [_6770,2|_6808], Downs: [_6524,3,_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: 3, U_1: _6770, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [1,_6500,2], Ups: [2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: 1, U_1: 2, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6808, Downs: [_6548,_6584,1,2|_6814]
Test        - Q : 4, Q_1: _6500, U_1: _7070, D_1: _6548
Test success
Result    -> I: 4, Qs: [3,1,4,2], Ups: [_6770,2,4|_7072], Downs: [_6524,3,4,_6584,1,2|_6814]
Qs = [3, 1, 4, 2] .

If you find it hard to read this output here because it is to wide and also hard to view as output to the top level (swipl.exe), then see how to use protocol/1 to capture the output to file for viewing and analysis.

Juju

Answer 3

Whitespace can help increase readability of a program greatly. Variables naming is also very important in that regard:

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

place_queens(0,_,_,_).
place_queens(    I,  QS,    US, [_|DS]) :- I > 0,
    I1 is I-1,
    place_queens(I1, QS, [_|US],   DS),
    place_queen( I,  QS,    US,    DS).

place_queen(     I,  QS,    US,    DS):-       % an equivalent definition!
   nth1(K,QS,I), nth1(K,US,I), nth1(K,DS,I).   % between(1,N,K) holds

The illustration from Willem's answer, again tweaked for whitespace:

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

Thus the recursion builds N nested N-long loops which the place_queen calls in effect are, working on the same lists with starting positions shifted in a certain scheme.

It will also make it so that UT = [U5,U6,U7,U8|_] (because of place_queen(4)) and DT = [D5,D6,D7,D8|_] (because of place_queen(1)), so the four loops will be equivalent to

four_queens( [Q1,Q2,Q3,Q4] ) :-
    place_queen(1, [Q1,Q2,Q3,Q4], [U2,U3,U4,U5], [D5,D6,D7,D8]),
    place_queen(2, [Q1,Q2,Q3,Q4], [U3,U4,U5,U6], [D4,D5,D6,D7]),
    place_queen(3, [Q1,Q2,Q3,Q4], [U4,U5,U6,U7], [D3,D4,D5,D6]),
    place_queen(4, [Q1,Q2,Q3,Q4], [U5,U6,U7,U8], [D2,D3,D4,D5]).

Indeed it produces the same results as queens(4, QS).

And we can kind of see the diagonals there.... Right? When a first queen is put at, say, Q3, it becomes 1=Q3=U4=D7,

four_queens( [Q1,Q2, 1,Q4] ) :- 
    place_queen(1, [Q1,Q2, 𝟭,Q4], [U2,U3, 𝟭,U5], [D5,D6, 𝟭,D8]),  % 1st row, 3rd pos
    place_queen(2, [Q1,Q2, 1,Q4], [U3, 1,U5,U6], [D4,D5,D6, 1]),
    place_queen(3, [Q1,Q2, 1,Q4], [ 1,U5,U6,U7], [D3,D4,D5,D6]),
    place_queen(4, [Q1,Q2, 1,Q4], [U5,U6,U7,U8], [D2,D3,D4,D5]).

and then it is impossible for the 2 queen to have been place_queened at either Q2 (taken by 1 on US) or Q4 (taken by 1 on DS). So the only other possibility is 2=Q1=U3=D4:

four_queens( [ 2,Q2, 1,Q4] ) :-
    place_queen(1, [ 2,Q2, 𝟭,Q4], [U2, 2, 1,U5], [D5,D6, 1,D8]),
    place_queen(2, [ 𝟮,Q2, 1,Q4], [ 𝟮, 1,U5,U6], [ 𝟮,D5,D6, 1]),  % 2nd row, 1st pos
    place_queen(3, [ 2,Q2, 1,Q4], [ 1,U5,U6,U7], [D3, 2,D5,D6]),
    place_queen(4, [ 2,Q2, 1,Q4], [U5,U6,U7,U8], [D2,D3, 2,D5]).

So because those lists were shifted by one position at each iteration step we ended up with the matrices with shared diagonal entries, so that claiming one cell on a diagonal claims it whole, automagically!

Next, 3=Q2 is impossible because D4=2 already. So we get 3=Q4=U7=D6,

four_queens( [ 2,Q2, 1, 3] ) :-
    place_queen(1, [ 2,Q2, 𝟭, 3], [U2, 2, 1,U5], [D5, 3, 1,D8]),
    place_queen(2, [ 𝟮,Q2, 1, 3], [ 2, 1,U5,U6], [ 2,D5, 3, 1]),
    place_queen(3, [ 2,Q2, 1, 𝟯], [ 1,U5,U6, 𝟯], [D3, 2,D5, 𝟯]),  % 3rd row, 4th pos
    place_queen(4, [ 2,Q2, 1, 3], [U5,U6, 3,U8], [D2,D3, 2,D5]).

and the answer is in sight!

four_queens( [ 2, 4, 1, 3] ) :-
    place_queen(1, [ 2, 4, 𝟭, 3], [U2, 2, 1,U5], [D5, 3, 1,D8]),
    place_queen(2, [ 𝟮, 4, 1, 3], [ 2, 1,U5, 4], [ 2,D5, 3, 1]),
    place_queen(3, [ 2, 4, 1, 𝟯], [ 1,U5, 4, 3], [ 4, 2,D5, 3]),
    place_queen(4, [ 2, 𝟰, 1, 3], [U5, 𝟰, 3,U8], [D2, 𝟰, 2,D5]).  % 4th row, 2nd pos

---

So the author's thought process could have been this. The chess board is a square matrix. What if placing a queen at some particular cell would automatically light up the whole column, can we do that? And the diagonals, too?

The key insight was that those are three separate views of the same board, and then it was probably easy to come up with these matrices:

           [[A, B, C, D],     [[E, F, G, H],     [[O, N, M, L],
            [A, B, C, D],      [F, G, H, I],      [P, O, N, M],
            [A, B, C, D],      [G, H, I, J],      [Q, P, O, N],
            [A, B, C, D]]      [H, I, J, K]]      [R, Q, P, O]]

and then they just needed a way of setting them up for any N automatically. It could've been coded with some arithmetic and a couple length and maplist calls, but it would've been much less mysterious and cool that way, so instead they inlined and simplified everything.

---

Another interesting thing to notice about this code is how it uses recursion to go to the base case in a linear fashion while setting up the stage for the following computation to be performed inside-out where the innermost recursion step of place_queen(1) actually becomes the outermost loop in the imperative nested loops interpretation of the generate-and-test model of nondeterministic computations.

It as if creates the code to be run first (the N nested loops for the given value of N), and then runs it.

_{(Something a Common Lisp, say, implementation might do with its macros; but using recursion instead. Or in functional paradigm we could say that it uses implicit continuations (at the second line in each predicate's definition, to be entered after the first recursive one returns) to emulate what could otherwise be achieved there by building such function to be run next explicitly, under continuation-passing style.)}

Farreaching

Answer 4

As an intermediate step to understanding the original program, you might consider the following, which is based on the same underlying idea. There is a variable for

• each of the N rows
• each of the 2*N-1 up-diagonals
• each of the 2*N-1 down-diagonals

These variables get instantiated with the column number of the queen that occupies the corresponding location on the board (because each queen covers a column, a row, an up-diagonal and a down-diagonal).

Instead of the clever list manipulation in the orginal program, this one uses "arrays" for the rows and diagonals, and is probably easier to understand:

queens(N, Rows) :-
    NDiag is 2*N-1,
    functor(Rows,  array, N),           % create the "arrays"
    functor(Ups,   array, NDiag),
    functor(Downs, array, NDiag),
    place_queen(1, N, Rows, Ups, Downs).

place_queen(C, N, Rows, Ups, Downs) :-
    ( C>N ->
        true
    ;
        between(1, N, R),
        arg(R, Rows, C),                % place column C queen in row R
        U is C-R+N, arg(U, Ups, C),     % ... and up-diagonal C-R+N
        D is C+R-1, arg(D, Downs, C),   % ... and down-diagonal C+R-1
        C1 is C+1,
        place_queen(C1, N, Rows, Ups, Downs)
    ).

Sigh

it would help greatly if you'd explained the numbering scheme for rows/columns/up/down diagonals explicitly. – Farreaching

Answer 5

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

Revis