Maximal Crossword Grids

Kevin K. Ferland 1, Robert W. Pratt 2
1Bloomsburg University, Bloomsburg, PA 17815
2SAS Institute Inc., Cary, NC 27513

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 \leq 49 \). Further, for all \( n \leq 30 \), all maximal grids are provided.