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:

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.

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.

Then

?-solution(S).

gives the answers.

 

Reference:

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

11 thoughts on “Eight Queens Problem in Prolog

  1. 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?

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

  3. 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?

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

Leave a comment

Your email address will not be published. Required fields are marked *