Wednesday, June 27, 2012

Solution of eight queens problem in Prolog

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.

Source Code:
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)]).
Output
A=4, B=2, C=7, D=3, E=6, F=8, G=5, H=1
A=5, B=2, C=4, D=7, E=3, F=8, G=6, H=1
A=3, B=5, C=2, D=8, E=6, F=4, G=7, H=1
A=3, B=6, C=4, D=2, E=8, F=5, G=7, H=1
A=5, B=7, C=1, D=3, E=8, F=6, G=4, H=2
A=4, B=6, C=8, D=3, E=1, F=7, G=5, H=2
A=3, B=6, C=8, D=1, E=4, F=7, G=5, H=2
A=5, B=3, C=8, D=4, E=7, F=1, G=6, H=2
A=5, B=7, C=4, D=1, E=3, F=8, G=6, H=2
A=4, B=1, C=5, D=8, E=6, F=3, G=7, H=2
A=3, B=6, C=4, D=1, E=8, F=5, G=7, H=2
A=4, B=7, C=5, D=3, E=1, F=6, G=8, H=2
A=6, B=4, C=2, D=8, E=5, F=7, G=1, H=3
A=6, B=4, C=7, D=1, E=8, F=2, G=5, H=3
A=1, B=7, C=4, D=6, E=8, F=2, G=5, H=3
A=6, B=8, C=2, D=4, E=1, F=7, G=5, H=3
A=6, B=2, C=7, D=1, E=4, F=8, G=5, H=3
A=4, B=7, C=1, D=8, E=5, F=2, G=6, H=3
A=5, B=8, C=4, D=1, E=7, F=2, G=6, H=3
A=4, B=8, C=1, D=5, E=7, F=2, G=6, H=3
A=2, B=7, C=5, D=8, E=1, F=4, G=6, H=3
A=1, B=7, C=5, D=8, E=2, F=4, G=6, H=3
A=2, B=5, C=7, D=4, E=1, F=8, G=6, H=3
A=4, B=2, C=7, D=5, E=1, F=8, G=6, H=3
A=5, B=7, C=1, D=4, E=2, F=8, G=6, H=3
A=6, B=4, C=1, D=5, E=8, F=2, G=7, H=3
A=5, B=1, C=4, D=6, E=8, F=2, G=7, H=3
A=5, B=2, C=6, D=1, E=7, F=4, G=8, H=3
A=6, B=3, C=7, D=2, E=8, F=5, G=1, H=4
A=2, B=7, C=3, D=6, E=8, F=5, G=1, H=4
A=7, B=3, C=1, D=6, E=8, F=5, G=2, H=4
A=5, B=1, C=8, D=6, E=3, F=7, G=2, H=4
A=1, B=5, C=8, D=6, E=3, F=7, G=2, H=4
A=3, B=6, C=8, D=1, E=5, F=7, G=2, H=4
A=6, B=3, C=1, D=7, E=5, F=8, G=2, H=4
A=7, B=5, C=3, D=1, E=6, F=8, G=2, H=4
A=7, B=3, C=8, D=2, E=5, F=1, G=6, H=4
A=5, B=3, C=1, D=7, E=2, F=8, G=6, H=4
A=2, B=5, C=7, D=1, E=3, F=8, G=6, H=4
A=3, B=6, C=2, D=5, E=8, F=1, G=7, H=4
A=6, B=1, C=5, D=2, E=8, F=3, G=7, H=4
A=8, B=3, C=1, D=6, E=2, F=5, G=7, H=4
A=2, B=8, C=6, D=1, E=3, F=5, G=7, H=4
A=5, B=7, C=2, D=6, E=3, F=1, G=8, H=4
A=3, B=6, C=2, D=7, E=5, F=1, G=8, H=4
A=6, B=2, C=7, D=1, E=3, F=5, G=8, H=4
A=3, B=7, C=2, D=8, E=6, F=4, G=1, H=5
A=6, B=3, C=7, D=2, E=4, F=8, G=1, H=5
A=4, B=2, C=7, D=3, E=6, F=8, G=1, H=5
A=7, B=1, C=3, D=8, E=6, F=4, G=2, H=5
A=1, B=6, C=8, D=3, E=7, F=4, G=2, H=5
A=3, B=8, C=4, D=7, E=1, F=6, G=2, H=5
A=6, B=3, C=7, D=4, E=1, F=8, G=2, H=5
A=7, B=4, C=2, D=8, E=6, F=1, G=3, H=5
A=4, B=6, C=8, D=2, E=7, F=1, G=3, H=5
A=2, B=6, C=1, D=7, E=4, F=8, G=3, H=5
A=2, B=4, C=6, D=8, E=3, F=1, G=7, H=5
A=3, B=6, C=8, D=2, E=4, F=1, G=7, H=5
A=6, B=3, C=1, D=8, E=4, F=2, G=7, H=5
A=8, B=4, C=1, D=3, E=6, F=2, G=7, H=5
A=4, B=8, C=1, D=3, E=6, F=2, G=7, H=5
A=2, B=6, C=8, D=3, E=1, F=4, G=7, H=5
A=7, B=2, C=6, D=3, E=1, F=4, G=8, H=5
A=3, B=6, C=2, D=7, E=1, F=4, G=8, H=5
A=4, B=7, C=3, D=8, E=2, F=5, G=1, H=6
A=4, B=8, C=5, D=3, E=1, F=7, G=2, H=6
A=3, B=5, C=8, D=4, E=1, F=7, G=2, H=6
A=4, B=2, C=8, D=5, E=7, F=1, G=3, H=6
A=5, B=7, C=2, D=4, E=8, F=1, G=3, H=6
A=7, B=4, C=2, D=5, E=8, F=1, G=3, H=6
A=8, B=2, C=4, D=1, E=7, F=5, G=3, H=6
A=7, B=2, C=4, D=1, E=8, F=5, G=3, H=6
A=5, B=1, C=8, D=4, E=2, F=7, G=3, H=6
A=4, B=1, C=5, D=8, E=2, F=7, G=3, H=6
A=5, B=2, C=8, D=1, E=4, F=7, G=3, H=6
A=3, B=7, C=2, D=8, E=5, F=1, G=4, H=6
A=3, B=1, C=7, D=5, E=8, F=2, G=4, H=6
A=8, B=2, C=5, D=3, E=1, F=7, G=4, H=6
A=3, B=5, C=2, D=8, E=1, F=7, G=4, H=6
A=3, B=5, C=7, D=1, E=4, F=2, G=8, H=6
A=5, B=2, C=4, D=6, E=8, F=3, G=1, H=7
A=6, B=3, C=5, D=8, E=1, F=4, G=2, H=7
A=5, B=8, C=4, D=1, E=3, F=6, G=2, H=7
A=4, B=2, C=5, D=8, E=6, F=1, G=3, H=7
A=4, B=6, C=1, D=5, E=2, F=8, G=3, H=7
A=6, B=3, C=1, D=8, E=5, F=2, G=4, H=7
A=5, B=3, C=1, D=6, E=8, F=2, G=4, H=7
A=4, B=2, C=8, D=6, E=1, F=3, G=5, H=7
A=6, B=3, C=5, D=7, E=1, F=4, G=2, H=8
A=6, B=4, C=7, D=1, E=3, F=5, G=2, H=8
A=4, B=7, C=5, D=2, E=6, F=1, G=3, H=8
A=5, B=7, C=2, D=6, E=3, F=1, G=4, H=8
92 Solutions

2 comments:

  1. Basically it's backtracking with generating permutations of 8 where the index(i) of the array is the row and the value (v[i]) is the column, plus a few more checks for diagonal moves.

    ReplyDelete
  2. Please would like to know if there is a possibility to make downloads of the code *. Pl

    This code shows the end of the run the amount of possibility exists to solve the problem of 8 queens?

    Leave the link available for download from the project ready format pl native prolog

    I'm waiting

    thank you

    ReplyDelete