Problem description:

Problem is often generalized to N queens – place N queens on an N × N
board so that no two attack each other (problem has no solution for N < 4). Any solution to the N queens problem will have a queen in each row and a queen in each column. I will use prolog to explain this problem, solutions can be specified as a permutation of the list of numbers 1 to N. The first element in the list is the row number of the queen in the first column, second element in the list is the row number of the queen in the second column and so on …

Prolog code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

% queens(+N,-Queens): Queens is a solution to the N-queens problem
queens(N,Qs) :-
    range(1,N,Us),
    queens(Us,[],Qs).
% queens(+Unplaced,?Placed,?Queens)
queens([],Qs,Qs).
queens(Us,Ps,Qs) :-
    select(Q,Us,Us1),
    \+ attack(Q,Ps),
    queens(Us1,[Q|Ps],Qs).
% range(+I,+J,-Ns): Ns is the list of integers between I and J inclusive
range(J,J,[J]).
range(I,J,[I|Ns]) :-
    I < J, I1 is I + 1, range(I1,J,Ns).
% attack(+Q,+Qs): queen in row Q attacks one or more of the queens in
% rows Qs on a diagonal
attack(Q,Qs) :- attack(Q,1,Qs).
attack(X,N,[Y|_]) :- X is Y + N.
attack(X,N,[Y|_]) :- X is Y - N.
attack(X,N,[_|Ys]) :-
    N1 is N + 1, attack(X,N1,Ys).

The function range is to generate a list from 1 to N, for example, range(1, 5, Ns), the Ns will be [1,2,3,4,5]. That provides the list of rows we can place our queens. The function attack considers only diagonals, because if one row has placed a queen, this row will be removed from our list, so the Qs only contains the row which the queens can be placed. Because we just place the queen in one column each time, so in the same column, we will never place two queens. So we only need to consider the diagonals. And for attack(X,N,[Y|_]) :- X is Y + N. considers the positive diagonals, the attack(X,N,[Y|_]) :- X is Y - N. considers the negative diagonals. 🙂

Comments: