Counting crossword puzzle grids with sufficiently long answers

Ben Coté1, Breeann Flesch2, Jasmine Hiebert3, Leanne Merrill4
1Math. Dept., Western Oregon University, Monmouth, OR 97361
2Business, Education, and Liberal Arts Division, Linn-Benton Community College, Albany, OR, 97321
3O’Fallon, IL
4Mathematics and Engineering Division, Lane Community College, Eugene, OR, 97405

Abstract

In this paper, we explore the enumerative combinatorics of American-style crossword puzzle grids under modified answer length requirements. While standard American-style crossword rules have a minimum answer length of three cells, we generalize this constraint to a minimum length \(m\) for an \(n\times n\) grid. We define \(\lvert Puz (n,m)\rvert\) as the number of such grids satisfying the standard structural rules of connectivity, \(180^\circ\) rotational symmetry, keyed squares, and full dimensionality. We prove that for \(m>\frac{n}{2}\), the number of valid grids is invariant under the transformation \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert\). Furthermore, we establish a closed-form formula for \(\lvert Puz (n,m)\rvert\) when \(m>\frac{n}{2}\). We also verify some counts for smaller grid dimensions verifying previously conjectured values.

Keywords: Crossword puzzle grids, enumerative combinatorics, integer sequences