# Minimum number of knights so that every cell is attacked

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$.

• 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. – kingW3 Jan 18 '15 at 19:56
• Does a cell count as attacked if a knight is on it? – Nate Jan 18 '15 at 21:16
• @Nate It doesn't count. – kingW3 Jan 18 '15 at 21:34
• @kingW3 I found 5 other solutions using 10 knights by a greedy approach. – Andrew Szymczak Jan 19 '15 at 23:29

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.

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.