10.1. Case Study I - 8 Queens Version 1.

8. Eight Queens

8.1. Case Study I - 8 Queens Version 1.

% From "Prolog - programming for artificial

% intelligence" by Ivan Bratko

% solution(BoardPosition) if BoardPosition is a list of

% non-attacking queens

solution([]).

solution([X/Y | Others]) :- % First queen at X/Y,

solution(Others), % other q's at Others

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

noattack(X/Y, Others). % First queen does

% not attack others

noattack(_, []). % nothing to attack

noattack(X/Y, [X1/Y1 | Others]) :-

Y =\= Y1, % different Y-coordinates

Y1-Y =\= X1-X, % different diagonal /

Y1-Y =\= X-X1, % different diagonal \

noattack(X/Y, Others).

member(Item, [Item | _]).

member(Item, [_ | Rest]) :-

member(Item, Rest).

% A solution template

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

8.2. Case Study I - 8 Queens Version 2.

% solution(Queens) if Queens is a list of Y-coordinates

% of eight non-attacking queens.

solution(Queens) :-

permutation([1,2,3,4,5,6,7,8], Queens),

safe(Queens).

permutation([], []).

permutation([Head | Tail], PermList) :-

permutation(Tail, PermTail),

del(Head, PermList, PermTail).

del(Item, [Item | List], List).

del(Item, [First | List], [First | List1]) :-

del(Item, List, List1).

safe([]).

safe([Queen | Others]) :-

safe(Others),

noattack(Queen, Others, 1).

noattack(_, [], _).

noattack(Y, [Y1 | Ylist], Xdist) :-

Y1-Y =\= Xdist,

Y-Y1 =\= Xdist,

Dist1 is Xdist + 1,

noattack(Y, Ylist, Dist1).

8.3. Case Study I - 8 Queens Version 3.

% Solution(YList) if YList is a list of Y-coordinates of

% eight non-attacking queens

solution(YList) :-

sol(YList,

[1, 2, 3, 4, 5, 6, 7, 8],

[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7],

[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 14, 13, 16]).

sol([], [], Dy, Du, Dv).

sol([Y | YList], [X | Dx1], Dy, Du, Dv) :-

del(Y, Dy, Dy1),

U is X-Y,

del(U, Du, Du1),

V is X+Y,

del(V, Dv, Dv1),

sol(YList, Dx1, Dy1, Du1, Dv1).

del(Item, [Item | List], List).

del(Item, [First | List], [First | List1]) :-

del(Item, List, List1).

8.4. Generalisation to N queens

To generalise example 3 to N queens we need to generate the domains automatically.

Need a procedure

gen(N1, N2, List).

which for two given integers produces a list

List = [N1, N1+1, N1+2, ..., N2-1, N2]

Such a procedure is

gen(N, N, [N]).

gen(N1, N2, [N1 | List]) :-

N1 < N2,

M is N1 + 1,

gen(M, N2, List).

The top level solution can then be generalized to

solution(N, S)

where N is the size of the board and S is the list of Y-coordinates for a valid solution.

General solution is

solution(N, S) :-

gen(1, N, Dxy),

Nu1 is 1-N, Nu2 is N-1,

gen(Nu1, Nu2, Du),

Nv2 is N+N,

gen(2, Nv2, Dv),

sol(S, Dxy, Dxy, Du, Dv).

and to obtain a solution (eg 12 queens) try

?- solution(12, S).

S = [1, 3, 5, 8, 10, 12, 6, 11, 2, 7, 9, 4]