Wednesday, June 27, 2012

Eight queen problem with solution in visual prolog (artificial intelligence)


Eight queens problem
Eight queens problem is a constraint satisfaction problem. The task is to place eight queens in the 64 available squares in such a way that no queen attacks each other. So the problem can be formulated with variables x1,x2,x3,x4,x5,x6,x7,x8 and y1,y2,y3,y4,y5,y6, y7,y8; the xs represent the rows and ys the column. Now a solution for this problem is to assign values for x and for y such that the constraint is satisfied.
The problem can be formulated as
P={(x1,y1),(x2,y2),……………………..(x8,y8)}
where (x1,y1) gives the position of the first queen and so on.

So it can be clearly seen that the domains for xi and yi are
Dx = {1,2,3,4,5,6,7,8}and Dy ={1,2,3,4,5,6,7,8} respectively.

The constraints are
i. No two queens should be in the same row,
i.e  yi≠yj for i=1 to 8;j=1 to 8;i≠j
ii. No two queens should be in the same column,
i.e  xi≠xj for i=1 to 8;j=1 to 8;i≠j
iii. There should not be two queens placed on the same diagonal line
i.e  (yi-yj) ≠ ±(xi-xj).

Now a solution to this problem is an instance of P wherein the above mentioned constraints are satisfied.

code in prolog

PREDICATES
DOMAINS
cell=c(integer, integer)
list=cell*
int_list=integer*

PREDICATES
solution(list)
member(integer,int_list)
nonattack(cell,list)

CLAUSES
solution([]).

solution([c(X,Y)|Others]):-
solution(Others),
member(Y,[1,2,3,4,5,6,7,8]),
nonattack(c(X,Y),Others).

nonattack(_,[]).
nonattack(c(X,Y),[c(X1,Y1)|Others]):-
Y<>Y1,
Y1-Y<>X1-X,
Y1-Y<>X-X1,
nonattack(c(X,Y),Others).

member(X,[X|_]).
member(X,[_|Z]):-
member(X,Z).


GOAL
solution([c(1,A),c(2,B),c(3,C),c(4,D),c(5,E),c(6,F),c(7,G),c(8,H)]).

1 comment:

  1. I just would like to give an enormous thumbs up for the nice information thanks for sharing. .
    best packers in patna.

    ReplyDelete