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$.
[Math] Minimum number of knights so that every cell is attacked
combinatorics
Best Answer
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.