Place as few knights as possible on an 8 by 8 chess board so that every square is controlled by at least one knight.

Question

Squares containing knights should be controlled as well. I think you need at least 3 knights to cover a corner, i.e. have the outside squares covered by knights, so that would be at least 12 knights to cover the board. 16 knights is the best I have done so far. I need to find the minimum and prove it's the minimum.

Answer 1

You can solve the problem via integer linear programming as follows. For each cell $(i,j)$, let $N_{i,j}$ be the set of neighbors (a knight's move away) of $(i,j)$, and let binary decision variable $x_{i,j}$ indicate whether a knight is placed on $(i,j)$. The problem is to minimize $\sum_{i,j} x_{i,j}$ subject to \begin{align} \sum_{(k,\ell)\in N_{i,j}} x_{k,\ell} &\ge 1 &&\text{for all $i,j$} &(\alpha_{i,j} \ge 0)\\ x_{i,j} &\ge 0 &&\text{for all $i,j$} &(\beta_{i,j} \ge 0)\\ \end{align} Here, the dual variables are indicated in parentheses. The linked page shows a solution that yields an upper bound of $14$. The following optimal dual values prove the lower bound: $$\alpha= \begin{pmatrix} 1 & 1/2 & 0 & 0 & 0 & 0 & 1/2 & 1 \\ 1/2 & 1/2 & 1/2 & 0 & 0 & 1/2 & 1/2 & 1/2 \\ 0 & 1/2 & 0 & 0 & 0 & 0 & 1/2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 0 & 1/2 & 0 \\ 1/2 & 1/2 & 1/2 & 0 & 0 & 1/2 & 1/2 & 1/2 \\ 1 & 1/2 & 0 & 0 & 0 & 0 & 1/2 & 1 \\ \end{pmatrix} $$ $$\beta= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} $$ As you can check, multiplying each constraint by its corresponding dual value and adding them all up will yield $\sum_{i,j} x_{i,j} \ge 14$.