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). |
تعليقات: 0
إرسال تعليق