Answers.Body: <p>There are many possible ways to encode this problem, and some will be more advantageous than others</p>
  
  <p>An encoding that seems like a reasonable starting point to me is:</p>
  
  <ol>
  <li>Variables: Let <span class="math-container">$S$</span> be a set of <span class="math-container">$k$</span> variables representing the coordinates of knights on the chess board.</li>
  <li>Domain: The domain of each variable is initially all vectors in <span class="math-container">$[n]^2$</span>. Denote the components of these vectors with <span class="math-container">$[r, c]$</span>.</li>
  <li>Constraints: 
  
  <ul>
  <li>Let A be the set of 8 attacking moves: <span class="math-container">$A=\{[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]\}$</span></li>
  <li><span class="math-container">$\forall_{i &lt; j} S_i \neq S_j$</span> (no knights on the same squares)</li>
  <li><span class="math-container">$\forall_{i &lt; j} [r_i, c_i] \notin \{[r_j + x, c_j + y] | x,y \in A\}$</span> (no knight attacks another knight)</li>
  </ul></li>
  </ol>
  
  <p>That should be it. Note the use of <span class="math-container">$\forall_{i&lt;j}$</span> in the constraints is to reduce the total number of constraints by half, exploiting the symmetry that knight <span class="math-container">$i$</span> can attack knight <span class="math-container">$j$</span> iff knight <span class="math-container">$j$</span> can attack knight <span class="math-container">$i$</span>. You could also use <span class="math-container">$\forall_{i\neq j}$</span>, but it would increase your constraint count to no gain.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-29T03:34:57.573Z
Answers.LastActivityDate: 2019-11-29T16:51:28.943Z
Answers.LastEditDate: 2019-11-29T16:51:28.943Z
Answers.UserDisplayName: John Doucette
Body: <p>There are three things in every constraint satisfaction problem (CSP):</p>
  
  <ol>
  <li>Variables</li>
  <li>Domain</li>
  <li>Constraints</li>
  </ol>
  
  <p>In the given scenario, I know how to identify the constraints, but I don't know how to identify the variables and the domain.</p>
  
  <p>The given scenario is:</p>
  
  <blockquote>
    <p>You are given a <span class="math-container">$n \times n$</span> board, where <span class="math-container">$n \geq 3$</span>. On this board, you have to put <span class="math-container">$k$</span> knights where <span class="math-container">$k &lt; n^2$</span>, 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 <span class="math-container">$3 \times 3$</span> board, we can place <span class="math-container">$k=5$</span> knights.</p>
  </blockquote>
  
  <p>So, the input is <span class="math-container">$m = 3, n = 3, k = 5$</span>. There are two solutions.</p>
  
  <p>Solution 1</p>
  
  <pre><code>K A K   
  A K A    
  K A K
  </code></pre>
  
  <p>Solution 2</p>
  
  <pre><code>A K A
  K K K
  A K A
  </code></pre>
  
Tags: <problem-solving><constraint-satisfaction-problems>
Title: How can I formulate the k-knights problem as a constraint satisfaction problem?
UserDisplayName: Sheri
ThreadText: # How can I formulate the k-knights problem as a constraint satisfaction problem?
  
  (Asked by: username_0 on 2019-11-28)
  
  There are three things in every constraint satisfaction problem (CSP):
  
  Variables
  Domain
  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
  
  **Tags:** problem-solving, constraint-satisfaction-problems
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-29. Score: 2 | Accepted answer
  
  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 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.
  
  
  ---
  
  