Question

The problem of placing k queens in an n×n chessboard. In this problem, you will be considering the problem of placing k knights in a n × n chessboard such that no two knights can attack each other. k is given and k ≤ n2.

a) Formulate this problem as a Constraint Satisfaction Problem. What are the variables?

b) What is the set of possible values for each variable?

c) How are the set of variables constrained?

Answer 1

Solution:

Here, the problem is about facing k knights on a n*n chess board such that, no two knights are attacking each other.

Given in problem, k and k ≤ n2.

a) From the Constraint Satisfaction Problem(CSP),

First of all a CSP has 3 components namely X (set of variables), D (set of domains), C (set of constraints).

There is a variable which is corresponding to each knight

And, there is a variable which is corresponding to each of the n2 positions on the board.

The variables about Constraint Satisfaction Problem, X^1, X^2,........, X^n are the knights.

b) The possible values are their X-Y coordinates for each variable.

location (X^1), ....................., location (X^k).

Each and every variable has two values here. Namely, Vacant and Occupied.

c) Here, the constraint for any 2 knights doesn't attack each other. Hence, that is the all difference between the variables (X^1, ......., X^k) and attacks (Xi, Xj) for any i and j values.

attacks (Xi, Xj) is true if the square of the distance between the location Xi and Xj is equal to 5.

i.e., if (a1, a2) be the coordinates of the location X1 and (b1, b2) be the coordinates of the location Xj then,