Eight Queens Problem in Prolog

The aim of this problem is to place eight queens on the empty chessboard in such a way that no queen attacks any other one. There will be three distinct solutions given.

Solution 1

At first, we need to define a representation of the board. Each square of chessboard can be represented by a pair of X and Y coordinates. We can write such pair as X/Y, where / is only for visual purposes. We know that each queen should be at a different row or column thus, we can define a template as [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]

We can generilize our solution with two cases. Case 1: THe list fo queens is empty. This is in fact a solution since there is no attack. Case 2. The list looks like this [X/Y|Others] Then we should look at three conditions for this case (1) There must be no attack in Others. Others must itself be a solution. (2) X and Y must be integers between 1 and 8. (3) X/Y must not attack any queen in Others. Our solution template means that all queens are in different columns. Then a) Y-coordinates should be different, b) they should not be in the same diagonal.  Then here is the algorithm:

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

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,
 Y1 - Y =\= X1 - X,
 Y1 - Y =\= X - X1,
 noattack(X/Y,Others).
 
member(Item,[Item|Rest]).
 
member(Item,[First|Rest]) :-
 member(Item,Rest).
 
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

After these

?- template(S), solution(S).

should give the solutions. Use ; to find more than one solution.

Solution 2

Here we do not explicity define x coordinates. It is automatically defined as 1,2,3… in a list in which Y coordinates are shown only. Solution then is in the form [Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8]. Where X coordinates are respectively 1,2,3,4,5,6,7,8.

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
27
28

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

Then

?-solution(S).

gives the answers.

Solution 3

Here is the last solution. It also gives the Y coordinates and X coordinates are predetermined as in the above solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

solution(Ylist) :-
 sol(Ylist,[1,2,3,4,5,6,7,8],
    [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,13,14,15,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).

Then

?-solution(S).

gives the answers.