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.

Reference:

Prolog Programming for Artificial Intelligence (4th Edition) (International Computer Science Series) (A great book!)

thanks alot

I have a question .if we want to determine the place of some queens and then solve the problem what should we do?

to zz:

For example in solution 1, you can change the template and take of the desired member from the list. I think that will solve your problem.

the codes were great help. thanks.

but i have a question. how should i go about it to make one for X number of queens on a X*X board?

can u tell what changes to be done while doing in turbo prolog

plz >>i need help

i didn’t understand what the raw (11)in solution (3) is ,

may you give an explanation.

also i need an explanation for the last raw in solution 1.

Thank you! Helped a lot!

where can i write use in solution 1 to show all the possible solutions ?!

Thx for information.

would you please provide me the key idea of prolog programming

Key idea:

http://en.wikipedia.org/wiki/Unification_(computer_science)tnx for information but what the output will looks like please?