2
$\begingroup$

Given a chess board of dimensions $7\times 7$ what is the minimal number of knights needed to be placed on the board so that every cell is attacked by at least one knight. I have no idea on this one.I assume the best strategy would be to put so that each knight attacks the most number of cells which is $8$.

$\endgroup$
  • 1
    $\begingroup$ The cells with a knight have to be attacked,I found the solution it's 10 knight and they are from c2 to c6 and from e2 to e6.Though I have no idea how did they get that solution. $\endgroup$ – kingW3 Jan 18 '15 at 19:56
  • 1
    $\begingroup$ Does a cell count as attacked if a knight is on it? $\endgroup$ – Nate Jan 18 '15 at 21:16
  • 1
    $\begingroup$ @Nate It doesn't count. $\endgroup$ – kingW3 Jan 18 '15 at 21:34
  • $\begingroup$ @kingW3 I found 5 other solutions using 10 knights by a greedy approach. $\endgroup$ – Andrew Szymczak Jan 19 '15 at 23:29
5
$\begingroup$

Using the natural ordering of squares of an $n \times n$ board $(i,j)\rightarrow ni+j$, here are optimal solutions for $n=4,5,6$. Clearly there are no solutions for $n < 4$.

$$ \begin{align} K(4) \; &: \; (0, 1, 5, 6, 10, 11) \\ K(5) \; &: \; (0, 1, 3, 6, 11, 12, 13) \\ K(6) \; &: \; (7, 8, 9, 10, 19, 20, 21, 22) \\ \end{align} $$

For $n=7$ I ran a brute force and exhausted all sets of < 10 knights. So, your solution of 10 knights is optimal.


I found a greedy algorithm that works pretty well -- I found 6 different optimal solutions for n=7.

$$ (3, 15, 16, 18, 19, 29, 30, 31, 32, 33) \\ (9, 11, 16, 18, 21, 25, 30, 32, 37, 39) \\ (9, 11, 16, 18, 23, 25, 30, 32, 37, 39) \\ (9, 11, 16, 18, 23, 27, 30, 32, 37, 39) \\ (15, 16, 17, 18, 19, 29, 30, 31, 32, 33) \\ (15, 16, 17, 18, 19, 29, 30, 32, 33, 45) \\ $$

First construct the $directed$ graph where each vertex is a square on the board and each edge $(u,v)$ represents a possible knight move from $u$ to $v$. Let's take a look at the adjacency matrix.

Adjacency Matrix

We want to find the smallest subset of rows (places to put the knights) such that each column remains non-empty (every square is attacked). This led me to do the following. Repeating until all pieces are attacked: greedily choose the safest spot on the board, that is, the non-attacked vertex $v^*$ with the minimum number of incoming edges. Let $u^*$ be the most aggressive of $v^*$s possible attackers. That is, let $u^*$ be the element in $\{ u \; | \; \exists \; (u,v^*) \} $ with the maximum number of outgoing edges. Let $U$ be the set of vertices that $u^*$ can attack $U = \{v \; | \; \exists \; (u^*,v)\}$. Place a knight on position $u^*$ and mark vertices in $U$ as attacked and remove all of their incoming edges.

Here is a visual of the first step. Note $v^*$ is the column with the least number of nonzero elements.

Greedy Iteration 1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.