From 8-Queens solution to more generic n-Queens solution in Prolog

Question

I am studying Prolog for an universitary exame and I have some problem with the following exercise.

I have the following classic solution of 8-Queens problem (and this is not a problem for me), Modifying this solution I have to create a new solution for the more generic n-Queens problem that handle a variable number of queens.

solution([]).

solution([X/Y|Others]) :- solution(Others),
                          member(Y,[1,2,3,4,5,6,7,8]),
                          noattack(X/Y, Others).

noattack(_,[]).

noattack(X/Y, [X1/Y1 | Others]) :-
                      Y =\= Y1,       % Q e Q1 sono su righe diverse
                      % Q e Q1 sono su diagonali diverse:
                      Y1-Y =\= X1-X,
                      Y1-Y =\= X-X1,
                      % Q non attacca regine nella sottolista Others:
                      noattack( X/Y, Others).

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

Ok, this program look pretty simple: I have a list of queen that have that they must not attack each other.

If the list of queen is empty there is not the possibility that a queen attack another queen in the list, so the empty list is a solution of the problem (it is the base case of the solution)

*If the list of queen is not empty I can divide it into [X/Y|Others] where X/Y rappresent position on the board of the first queen in the list *(the position is rappresentend by the couple (X,Y) where X is the column and Y the line)

So, it is TRUE that the list [X/Y|Others] is a SOLUTION of the problem if the following relations are true:

The sublist Others is itself a solution (Others don't contain queen that attack some other queen in the list)
Y belongs belongs to an integer value between 1 and 8 (because I have 8 line)
The first queen of the list don't attacck the others queens in the sublist Others

Then it is defined the noattack relation that specify when I can say that it is true that a queen don't attack another queen (this is pretty simple: they can't stay on the same line, on the same column, on the same diagonal)

Finally I have a solution template that simplify my life constraining the X value with value from 1 to 8 (because I know that 2 queens can't stay on the same columns...so every queen in the solution stay on a different column from all others queens)

So I think that the biggest problem it is on the line in which I specify the number of columns:

member(Y,[1,2,3,4,5,6,7,8])

and on the line in which I define the solution template:

template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

I have no idea about how to extend the previous solution to handle a variable number of queens.

CapelliC CapelliC · Accepted Answer · 2013-04-05T19:42:11

seems easy, passing around the size:

solution(_, []).
solution(N, [X/Y|Others]) :-
    solution(N, Others),
    between(1, N, Y),
    noattack(X/Y, Others).

noattack(_,[]).
noattack(X/Y, [X1/Y1 | Others]) :-
    Y =\= Y1,       % Q e Q1 sono su righe diverse
    Y1-Y =\= X1-X,  % Q e Q1 sono su diagonali diverse
    Y1-Y =\= X-X1,
    noattack( X/Y, Others). % Q non attacca regine nella sottolista Others

% TEMPLATE DELLE SOLUZIONI: c'è una regina su ogni colonna:
template(N, L) :-
    findall(I/_, between(1,N,I), L).

test:

?- N=6, template(N, L), solution(N, L).
N = 6,
L = [1/5, 2/3, 3/1, 4/6, 5/4, 6/2] ;
N = 6,
L = [1/4, 2/1, 3/5, 4/2, 5/6, 6/3] ;
N = 6,
L = [1/3, 2/6, 3/2, 4/5, 5/1, 6/4] ;
N = 6,
L = [1/2, 2/4, 3/6, 4/1, 5/3, 6/5] ;
false.

(I should draw it to say if it's ok...)

From 8-Queens solution to more generic n-Queens solution in Prolog

1 Answers