Scribd
Upload
15 views2 pages

8-Queens Problem in PROLOG

This document summarizes an approach to solving the 8-queens problem using Prolog. It represents the chessboard as a list of queen positions, defines a solution predicate to return valid solutions, and uses constraints to ensure queens don't attack each other by being in the same row, column or diagonal. It breaks the problem down into base cases of an empty board and board with queens, and defines a nonattack predicate to check each queen addition doesn't cause attacks.

Uploaded by

Jaymit Surve
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
15 views2 pages

8-Queens Problem in PROLOG

This document summarizes an approach to solving the 8-queens problem using Prolog. It represents the chessboard as a list of queen positions, defines a solution predicate to return valid solutions, and uses constraints to ensure queens don't attack each other by being in the same row, column or diagonal. It breaks the problem down into base cases of an empty board and board with queens, and defines a nonattack predicate to check each queen addition doesn't cause attacks.

Uploaded by

Jaymit Surve
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

252 Yash Gujar

8 – Queen Problem Using PROLOG

PROBLEM STATEMENT: - Placing 8-queens on a chessboard such that they don’t attack
each other.

EXPLANATION:

 We first take chess-board of 8*8 grid.


 After that we represent the board as a list of eight elements.i.e. [X1:Y1, X2:Y2,
X3:Y3, X4:Y4, X5:Y5, X6:Y6, X7:Y7, X8:Y8] where X represents the column, Y
represents the row and each X:Y represents the position of one queen on the board.
 After that we define a predicate: - solution (list) which returns the solution in a list.
 Now the statement Y<>Y1 represents different rows and Y1-Y<>X1-X, Y1-Y<>X-
X1 represents different diagonals which are to be selected.
 Now to avoid vertical attacks, queens have to be on different columns, so we may fix
the X coordinates to achieve this. i.e. [1:Y1,2:Y2,3:Y3,4:Y4,5:Y5,6:Y6,7:Y7,8:Y8]
 After that we may break the problem down to two cases of having an empty list or a
list with a head and a tail as we usually do with problems involving lists.

Case_1

There are no queens on the board then the no attack condition holds and we have:
solution([ ])

Case_2

There are some queens on the board in this case the list will be [c(X,Y)|Others]
where c(X,Y) represents position of first queen and Others represent other queens.

 In such a case, there will a solution if

1) No attacks between the queens in Others


2) X and Y are integers between 1-8
3) A queen at square X:Y must not attack any of the queens I the list Others

 After that we define the predicate: nonattack(Queen,List_of_Queens). This can


again be broken into two cases.

Case_1

If the List_of_Queens is empty then there are no queens to be attacked:


nonattack(_,[])

Case_2

If the List_of_Queens is not empty then it can be represented as


[Queen1|Rest_of_Queens]
and we must check two conditions:
1) The queen at position Queen must not attack the one at position Queen1
2) The queen at position Queen must not attack the ones in the Rest_of_Queens

CODE:

OUTPUT:

You might also like