Maximal Crossword Grids

Abstract

The maximum number of clues in an $n\times n$ American-style crossword puzzle grid is explored. Grid constructions provided for all $n$ are proved to be maximal for all even $n$. By using mixed integer linear programming, they are verified to be maximal for all odd $n\le 49$. Further, for all $n\le 30$, all maximal grids are provided.