On the \(n \times n\) Knight Cover Problem

Abstract

A set of Knights covers a board if a Knight attacks every unoccupied square. What is the minimum number of Knights in a cover of an \(n\times n\) board? For \(n \leq 10\), we give a non-computational proof that the widely accepted answers are correct. For \(n \leq 14\), fractional Knight packings are used in an exhaustive branch-and-bound program. This gives the first enumeration of minimum Knight covers for \(11 \leq n \leq 14\). For \(n \geq 15\), integer programs are used to find small (though not necessarily minimum) symmetric covers. This yields smaller covers for \(16 \leq n \leq 19\), and new covers when \(21 \leq n \leq 25\). Simulated annealing discovered yet smaller covers for \(n = 19\) and \(n = 21\). Guess work improved the results for \(n = 20\) and \(n = 25\).