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 x

The problem can be formulated as _{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}and y_{1},y_{2},y_{3},y_{4},y_{5},y_{6,}y_{7},y_{8}; 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.P={(x_{1},y_{1}),(x_{2},y_{2}),……………………..(x_{8},y_{8})} where (x_{1},y_{1}) gives the position of the first queen and so on. So it can be clearly seen that the domains for x_{i }and y_{i}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 y_{i}≠y_{j} for i=1 to 8;j=1 to 8;i≠j |

ii. No two queens should be in the same column, |

i.e x_{i}≠x_{j }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 (y_{i}-y_{j}) ≠ ±(x_{i}-x_{j}). |

**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)]).

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

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.

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

ReplyDeleteThis 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