How can I formulate the k-knights problem as a constraint satisfaction problem?

Question

There are three things in every constraint satisfaction problem (CSP):

1. Variables
2. Domain
3. Constraints

In the given scenario, I know how to identify the constraints, but I don't know how to identify the variables and the domain.

The given scenario is:

You are given a $n \times n$ board, where $n \geq 3$. On this board, you have to put $k$ knights where $k < n^2$, such that no knight is attacking the other knight. The knights are expected to be placed on different squares on the board. A knight can move two squares vertically and one square horizontally or two squares horizontally and one square vertically. The knights attack each other if one of them can reach the other in a single move. For example, on a $3 \times 3$ board, we can place $k=5$ knights.

So, the input is $m = 3, n = 3, k = 5$. There are two solutions.

Solution 1

K A K   
A K A    
K A K

Solution 2

A K A
K K K
A K A

Answer 1

There are many possible ways to encode this problem, and some will be more advantageous than others

An encoding that seems like a reasonable starting point to me is:

1. Variables: Let $S$ be a set of $k$ variables representing the coordinates of knights on the chess board.
2. Domain: The domain of each variable is initially all vectors in $[n]^2$. Denote the components of these vectors with $[r, c]$.
3. Constraints:
   • Let A be the set of 8 attacking moves: $A=\{[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]\}$
   • $\forall_{i < j} S_i \neq S_j$ (no knights on the same squares)
   • $\forall_{i < j} [r_i, c_i] \notin \{[r_j + x, c_j + y] | x,y \in A\}$ (no knight attacks another knight)

That should be it. Note the use of $\forall_{i<j}$ in the constraints is to reduce the total number of constraints by half, exploiting the symmetry that knight $i$ can attack knight $j$ iff knight $j$ can attack knight $i$. You could also use $\forall_{i\neq j}$, but it would increase your constraint count to no gain.