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.
The mathematical study of crossword puzzles contains a surprising number of connections to other areas of mathematics and is a ripe environment for finding and answering open questions. In this paper, we demonstrate the sorts of arguments that can be made to answer these questions and prove a conjecture regarding an integer sequence arising in American-style crossword puzzles with modified answer length requirements (see [7]):
To begin, we define the objects of study in this paper to clarify what we mean by “crossword puzzle.”
Definition 1.1. The set \(Grid (n)\) is the set of \(n\times n\) grids of squares, where each square is either white or black. The white squares are called cells and the black squares are called voids. The boundary of a grid in \(Grid (n)\) refers to perimeter of the grid, composed of four edges we call the north, south, east, and west. The edges meet at four corners, which we refer to as the northwest, northeast, southwest, and southeast corners respective of the edges which meet there.
Not all elements of \(Grid (n)\) look like crossword puzzles; for instance, a traditional chessboard would be an element of \(Grid (8)\) but lacks some of the qualities we would expect to see in a crossword puzzle grid. We now focus on the types of grids that correspond to commonly seen crossword puzzles in the United States.
To support the upcoming definition, we introduce a piece of vocabulary related to crossword construction.
Definition 1.2. Let \(X\in Grid (n)\). A maximal vertical sequence of adjacent cells in \(X\) is a Down answer, and likewise a maximal horizontal sequence of cells in \(X\) is called an Across answer.
We are now ready to define the primary object of study.
Definition 1.3. An American-style crossword puzzle grid is an element of \(Grid (n)\) satisfying certain structure rules (see [11]):
1. (Connectivity) Any two cells in the grid are connected via a path traveling only through cells using horizontal or vertical steps. In other words, the voids in a puzzle do not “break up” the set of cells into smaller, disconnected sets;
2. (\(180^\circ\) rotational symmetry) The grid must possess rotational symmetry. That is, when it is rotated \(180^\circ\), the grid must look the same;
3. (Answer length) All answers must be at least three cells long;
4. (Keyed squares) Each cell must keyed; that is, each cell must be part of both an Across and a Down answer;
5. (Full dimension) There cannot be a full row or column of voids along the boundary of the grid.
An example of such a puzzle can be seen in Figure 1. A \(15\times 15\) grid was chosen for this example because that is the most common size seen in weekday newspapers published in the United States.
Prior mathematical results related to American-style crossword puzzles are scant but growing in number. Both McSweeney [8] and Ferland [3], [4] describe crossword puzzles mathematically. Outside of academic mathematics, the website FiveThirtyEight posed a question in a 2019 Riddler Column [9]: how many (\(15\times 15\), American-style) crossword puzzles can you make? Jim Ferry answered this question [10] using dynamic programming (see [5]); the answer is over 400 trillion puzzles.
Two authors of this paper have studied properties of standard American-style puzzles in [2] and [1] using combinatorial and graph-theoretic techniques. Grid counting questions form a major theme of this work: how many grids of a given size exist, satisfying certain modified structure rules?
We consider what happens when we alter the answer length requirement in an American-style crossword puzzle grid. Specifically, we ask whether we can count the total number of \(n\times n\) grids with answer length greater than or equal to a fixed value \(m\).
Definition 2.1. We denote by \(Puz (n,m)\) the set of all \(n\times n\) crossword puzzle grids with minimum world length \(m\).
We are interested in the cardinalities \(\lvert Puz (n,m)\rvert\), which are displayed in Table 1, which was generated but the third author in her undergraduate research project. The following discussion establishes some of the easier-to-find entries.
If \(m>n\), no such puzzles exist, since answers must fit inside the grid. If \(m=n\), there is exactly one such puzzle: the puzzle containing all cells and no voids. In this puzzle there are \(m=n\) Across answers and \(m=n\) Down answers, all of length \(m=n\). Together, these observations establish the upper triangle of 0 entries and the main diagonal of 1’s.
However, when \(m<n\), several interesting patterns begin to occur. For instance, the reader may notice the subdiagonal of 3’s beginning at \(n=3\), \(m=2\) and continuing for all \(m=n-1\) with \(m\geq 2\). In these puzzles, the minimum answer length is one less than the puzzle size. Application of the structure rules reveals that only three puzzles satisfy all the conditions: the puzzle with no voids, and then the two puzzles that have a pair of voids in antipodal corners of the puzzle. The addition of any more voids would result in an answer length less than \(n-1\). Thus, there are only three puzzles in this family for \(m=n-1\) when \(n\geq 3\). We invite the reader to explain why there is a single puzzle allowed (the voidless puzzle) when \(n=2\) and \(m=1\).
| Minimum answer length \(m\) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 11 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | ? | 10 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | ? | 57* | 12 | 3 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | ? | ? | 48* | 12 | 3 | 1 | 0 | 0 | 0 | 0 |
| 7 | ? | ? | 312* | 50* | 12 | 3 | 1 | 0 | 0 | 0 |
| 8 | ? | ? | ? | ? | 50* | 12 | 3 | 1 | 0 | 0 |
| 9 | ? | ? | ? | ? | ? | 50* | 12 | 3 | 1 | 0 |
| 10 | ? | ? | ? | ? | ? | ? | 50* | 12 | 3 | 1 |
| 11 | ? | ? | ? | ? | ? | ? | ? | 50* | 12 | 3 |
Similarly, another subdiagonal of 12’s begins at \(n=5,m=3\). In this case, all voids must once again be adjacent to corners, as a void introduced in the interior of the puzzle, or along the middle of an edge, would immediately result in an answer length of 1 or 2. Since \(m=n-2\) for these puzzles, the top row cannot have more than two voids, and these voids can be adjacent or in opposite corners. Likewise, along the left side, there cannot be more than two voids, either in separate corners or adjacent to one another. This reasoning, along with the use of symmetry and the keyed squares rule, allows for an exhaustive counting of void arrangements. It is helpful to organize the puzzles by the number of voids they contain (in this case, 0, 2, 4, 6 or 8 voids). Only even numbers are possible due to symmetry and the inability to put voids in the interior of the puzzle. All \(5\times 5\) puzzles are shown in Figure 2. Other values where \(m=n-2\) have the same corner void arrangements with additional rows and columns of cells in the interior of the puzzle.
Several of the other entries in Table 1 can be found using elementary techniques. For instance, calculating the entry corresponding to \(m=1, n=3\) requires counting all \(3\times 3\) puzzles with minimum word length \(m=1\), but obeying all other structure rules (connectivity, \(180^\circ\) rotation symmetry, keyed squares, and full dimension). When \(m=1\), all squares are automatically keyed as a single cell represents an entire answer. The full dimension and connectivity rules eliminate any puzzles that contain a full row or column of voids. With these constraints, along with symmetry, it is fairly quick to count all 11 puzzles satisfying the structure rules with \(m=1\), as seen in Figure 3. Note that of these puzzles, 3 of them have \(90^\circ\) rotational symmetry, and the 8 occur in 4 pairs, each member of which can be obtained from a \(90^\circ\) rotation from the other member of the pair.
Other counting problems are more challenging. The entries 47 and 57 have been counted systematically by hand (see Section 7). When \(n=7\) and \(m=3\), voids needn’t be adjacent to the corners; for example, consider the \(7\times 7\) grid with a single void in the center of the puzzle, which would satisfy all structure rules. The entry 312 on the table was counted carefully by members of an undergraduate research course and has been independently verified by a crossword puzzle construction group (see [6]). Nevertheless, by-hand counting techniques become unwieldy quickly in much of the lower triangle of the table. The entry in \(n=15\), \(m=3\) corresponds to the 400 trillion number found computationally by Ferry (see [5]).
The value for \(n=6\), \(m=3\) can be found more easily by hand, in part due to the lack of interior voids. The reader is invited to check this number themselves, and indeed the authors of this paper initially found this number using an exhaustive counting process. It was then used as inspiration for part (b) of Theorem 4.6 later in this paper.
We hope we have convinced the reader that filling in this table is a challenging but worthwhile process. The remainder of this paper is devoted to proving several theorems that explain the persistent subdiagonals on this table, relating them to a known sequence arising in a completely separate mathematical context.
In this section we establish results concerning the allowable placement of voids when the minimum word length is at least half of the dimension of the grid. In particular, we describe when such voids can occur in the middle square(s) of a row/column and show that every void must be path connected to exactly one corner. This is our first step in calculating some of the recurring numbers in Table 1.
We use the term center row(s) and center column(s) to refer to the single center row/column if the dimension of the grid is odd, and the two center rows/columns if the dimension of the grid is even.
Lemma 3.1. Let \(X\in Puz (n,m)\) and suppose \(m>\frac{n}{2}\). Then the center row(s) and center column(s) of \(X\) are voidless.
Proof. Suppose for sake of contradiction that there is a void within the center row(s) or center column(s) of \(X\). If the full row or column is voided then we break connectivity, so there must be at least one answer in the corresponding row and one answer in the corresponding column, each occurring on one side or the other of this void. Since we assumed the void occurred within the center row(s) or center column(s), there are at most \(\frac{n}{2}\) available cells between this void and at least one edge of the grid, creating an answer of length at most \(\frac{n}{2}\). But since the minimum answer length \(m\) satisfies \(m>\frac{n}{2}\), this is a contradiction. A similar argument applies to rows. ◻
Lemma 3.2. Let \(X\in Puz (n,m)\) with \(n\) even, and suppose \(m=\frac{n}{2}\). Then any row or column of \(X\) may contain at most one void in the center squares of that row or column.
Proof. Suppose for some even \(n\) and \(m=\frac{n}{2}\) we have a grid \(X\in Puz (n,m)\). Each row and column has two center squares. We want to show that they cannot both be voids. Suppose to the contrary that they are both voids. On either side of the center voids, there are \(\frac{n-2}{2}\) remaining squares. If any of these is a cell, then it must belong to an answer within that row/column due to the keyed condition. However, \(\frac{n-2}{2}<\frac{n}{2}=m\), so such an answer would break the minimum length condition. Thus, all the squares in this row/column must be voids, which violates the full dimension or the connectivity structure rule, depending on whether our row/column is along an edge. Thus, no row or column in \(X\) can have both center squares voided. ◻
See Figure 5 for a demonstration of Lemmas 3.1 and 3.2.
Corollary 3.3. Let \(X\in Puz (n,m)\) and suppose \(m\geq\frac{n}{2}\). Then any void must be connected to either the north or south edge by a vertical path of voids, and similarly must be connected to either the east or west edge by a horizontal path of voids.
Proof. If \(m>\frac{n}{2}\), then by Lemma 3.1, the center row(s) and column(s) are voidless, so a void cannot be equal distance from the east and west edge, and cannot be equal distance from the north and south edge. If \(m=\frac{n}{2}\), then any void cannot be equal distance from opposite edges. Thus, if \(m\geq\frac{n}{2}\), any void must have exactly two nearest non-opposite edges, both of which are fewer than \(\frac{n}{2}\) squares away. We wish to show that such a void must be path connected via horizontal and vertical paths of voids to the nearest edges. Assume to the contrary that a cell exists between this void and a nearest edge. Then by the keyed condition, that cell must be part of an answer between the void and the nearest edge. However, any such answer would have fewer than \(\frac{n}{2}\) cells, breaking the length condition since \(m\geq\frac{n}{2}\). Thus, no cells can exist between a void and its nearest edges. ◻
Corollary 3.4. Let \(X\in Puz (n,m)\) and suppose \(m\geq\frac{n}{2}\). Then every void in \(X\) must be connected by a path of voids to exactly one corner.
Proof. Suppose \(X\in Puz (n,m)\) with \(m\geq\frac{n}{2}\). By Corollary 3.3, each void in \(X\) is connected by a path of voids to exactly one of the east or west edges. Taking the final void in this path and again applying Corollary 3.3, there is a vertical path to exactly one of the north or south edges. Thus, each void is path connected to a corner. We now must demonstrate that there cannot be a path to two corners. If \(m>\frac{n}{2}\), then by Lemma 3.1, the center row(s) and column(s) are voidless. If \(m=\frac{n}{2}\), then by Lemma 3.2, no adjacent voids can exist in the center row(s) and column(s). Both conditions prevent any path of voids from connecting two corners. ◻
Definition 3.5. When considering an \(X\in Puz (n,m)\) with \(m\geq\frac{n}{2}\), we denote by \(NW, NE, SE, SW\) the set of voids path connected to the northwest, northeast, southeast, and southwest corners, respectively.
By Corollary 3.4, these sets, excluding any which are empty, form a partition of the set of voids. We now examine the structure of the connected components of voids, and due to rotational symmetry we may restrict our attention to \(NW\) and \(NE\).
Lemma 3.6. Suppose \(X\in Puz (n,m)\) with \(m\geq\frac{n}{2}\) and let \(d=n-m\). Then the following conditions on the void components \(NW\) and \(NE\) must be satisfied:
(1) in any row when going west to east the voids in \(NW\) must occur prior to any cells, which must occur prior to any voids in \(NE\)
(2) in any column, voids from \(NW\) and \(NE\) may not occur below cells.
(3) in any column, there cannot be voids from both \(NW\) and \(NE\)
(4) in any row the components \(NW\) and \(NE\), together, contain at most \(d\) voids
(5) the westernmost column of \(NW\) and the easternmost column of \(NE\), together, contain at most \(d\) voids.
Proof. Conditions (1), (2), and (3) follow directly from Corollary 3.3. By Lemmas 3.1 and 3.2, there must be an answer, and hence at least \(m\) cells, in each row. Thus, there can be at most \(d=n-m\) voids, proving condition (4). For condition (5), notice that, by symmetry, the easternmost column of \(NE\) contains the same number of voids as the westernmost column of \(SW\). By the full dimension rule, the westernmost column must contain an answer between the \(NW\) and \(SW\) voids, so by our assumption on the answer length condition it must contain at least \(m\) cells. Thus, the westernmost column of \(NW\) and the easternmost column of \(NE\) together can contain at most \(d=n-m\) voids. ◻
Theorem 3.7. Suppose \(X\in Puz (n,m)\) with \(m\geq\frac{n}{2}\). Then the puzzle \(X\) is completely determined by the structure of the voided components \(NW\) and \(NE\) and the value \(n\).
Proof. By Corollary 3.4, all voids in \(X\) are path connected to exactly one corner. By symmetry, the configuration of the voids in \(NE\) determines the configuration of the voids in \(SW\) and likewise \(NW\) determines \(SE\), so the two northern configurations determine the entirety of \(X\). ◻
In the situation where our middle row(s) and column(s) are voidless, we have a way to compare values diagonally adjacent in Table 1. We first establish several maps between puzzles of different sizes and show that they preserve the structure rules under certain conditions. These maps will allow us to prove the desired relationships between puzzles.
Definition 4.1. We define the deletion map \(d\colon Puz (n+1,m+1)\to Puz (n,m)\) based on the parity of \(n+1\). If \(n+1\) is odd, then \(d\) deletes the middle row and column of \(X\). If \(n+1\) is even, then \(d\) deletes the westernmost center column \(X\) and the northernmost center row of \(X\).
Definition 4.2. In the other direction, we define the extension map \(e\colon Puz (n,m)\to Puz (n+1,m+1)\) which inserts a row and column of cells into the middle of a grid, again, depending on the parity of the input. Let \(X'\in Puz (n,m)\). Then if \(n\) is even, \(e(X')\) is obtained by inserting a row and column of cells along the horizontal and vertical midlines of \(X'\). If \(n\) is odd, \(e(X')\) is obtained by inserting a row of cells north of the middle row and a column of cells west of the middle column of \(X'\).
Lemma 4.3. For \(m\geq\frac{n}{2}\), the map \(d\colon Puz (n+1,m+1)\to Puz (n,m)\) preserves the structure rules as stated in Definition 1.3.
Proof. Let \(X\in Puz (n+1,m+1)\). This means that \(X\) has minimum answer length of \(m+1\). Then in \(d(X)\), a row and column were deleted from \(X\), so at most one cell was deleted from any particular answer, so \(d(X)\) is an \(n\times n\) grid with minimum answer length \(m\). To show that \(d(X)\) is connected and symmetric, recall that \(m>\frac{n}{2}\). Therefore, we know \[m+1>\frac{n}{2}+1.\]
This inequality will allow us to compute the maximum number of voids in a row or column by taking the dimension minus the minimum word length. In this case we get \((n+1)-(m+1)\). By the inequality above, we get \[\begin{aligned} (n+1)-(m+1)&<(n+1)-\left(\frac{n}{2}+1\right)\\ &=n-\frac{n}{2}\\ &=\frac{n}{2} \end{aligned}\] showing the maximum number of voids in a row or column of our \((n+1)\times(n+1)\) grid is \(\frac{n}{2}-1\) if \(n\) is even and \(\frac{n-1}{2}\) if \(n\) is odd. Thus, \(X\) must have the center 2 or 3 rows/columns voidless, depending on the parity of \(n\). Either way, \(d(X)\) removes one of these rows/columns while maintaining connectivity and symmetry. To demonstrate that squares remain keyed in \(d(X)\), note that the only ways to violate this would be to break connectivity, which we’ve already demonstrated is impossible, or to create an answer length less than \(m\), which cannot happen because the range lies inside the codomain. Finally, we see that \(d(X)\) has full dimension when \(n+1\) is even because there continues to be at least one row and column of cells in the middle of \(d(X)\). When \(n+1\) is odd, there must also be at least one cell along each edge; otherwise, there would have been an answer of length \(m+1=1\) in \(X\) we know that \(m\) is a positive integer. Thus, the map \(d\colon Puz (m+1,n+1)\to Puz (m,n)\) preserves the structure rules as desired. ◻
Lemma 4.4. For \(m\geq\frac{n}{2}\), the map \(e\colon Puz (n,m)\to Puz (n+1,m+1)\) preserves the structure rules as stated in Definition 1.3.
Proof. Let \(X'\in Puz (m,n)\). Then \(e(X')\) is a \((n+1)\times(n+1)\) puzzle with minimum word length \(m+1\) since we are adding one to the length of each answer and increasing the size of the grid by one row and one column. Further, inserting rows and columns of cells does not un-key any squares or break connectivity or full dimension. To see the \(e(X')\) has \(180^\circ\) rotational symmetry, consider cases based on whether \(n\) is even or odd. If \(n\) is even, inserting a row and column of cells directly in the center of grid preserves symmetry. If \(n\) is odd, the inserted row and column of cells are paired with the original “center” row and column of cells from \(X'\), once again preserving symmetry. Therefore, \(e\) also preserves the structure rules. ◻
Lemma 4.5. The maps \(d\) and \(e\) are mutually inverse bijections when \(m>\frac{n}{2}\).
Proof. Let \(X\in Puz (n+1,m+1)\) with \(m>\frac{n}{2}\). If \(n+1\) is odd, \(e(d(X))=X\) because this composition produces the grid obtained by deleting the middle row and column of cells from \(X\) to create an even-sized grid, and then inserting a row and column of cells above and to the left of the horizontal and vertical midlines respectively, producing a grid identical to \(X\). Likewise, if \(n+1\) is even, then \(e(d(X))=X\) because this composition deletes the row and column of cells above and to the left of the horizontal and vertical midlines respectively, producing an odd-size grid, and then inserting a row and column of cells above and above and to the left of the middle row and column respectively, once again producing a grid identical to \(X\). Thus \(d\) and \(e\) are mutually inverse bijections. The equality \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert\) follows. ◻
Theorem 4.6. Let \(n\) be a natural number and let \(m\geq\frac{n}{2}\). Then:
(1) if \(m>\frac{n}{2}\), we have \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert\).
(2) if \(n\) is even and \(m=\frac{n}{2}\), we have \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert-2\).
Proof. Part (1) follows directly from Lemmas 4.3, 4.4, and 4.5. To demonstrate part (2), let \(n\) be even. Suppose you have an \((n+1)\times(n+1)\) puzzle satisfying a condition of lower bound of \(m+1\) on answer length. Then upon deleting the center row and column, we are left with an \(n\times n\) puzzle with minimum answer length \(m\). The resulting puzzle will satisfy all other necessary conditions, unless removing the center row and column results in a loss of path connectivity. Connectivity could only be broken if two voids become adjacent at an edge or corner. The minimum answer length condition prevents a row/column removal from resulting in two voids becoming edge adjacent. However, removing the center row and column may result in voids becoming corner adjacent at the center of the grid. There are two ways this could happen, exactly the two ways a \(\frac{n}{2}\times\frac{n}{2}\) block of voids could exist in the puzzle. ◻
See Figure 6 for an example of one such exceptional puzzle. This is related to the the twelve \(5\times 5\) puzzles in Figure 2 satisfying \(m=3\). We could obtain twelve \(4\times 4\) grids by removing the center row and center column from each of the twelve \(5\times 5\) puzzles. All 12 such grids would satisfy \(m=2\), but the outermost puzzles would result in a loss of path connectivity, as the connected components of voids would meet at a corner. This gives \(\lvert Puz (4,2)\rvert=10\) while \(\lvert Puz (5,3)\rvert=12\).
Corollary 4.7. If \(m\geq\frac{n}{2}\), then \(\lvert Puz (n,m)\rvert\) is a function of \(d=n-m\).
We now turn our attention to determining a formula for \(\lvert Puz (n,m)\rvert\) when we have a fixed \(d=n-m\) and \(m>\frac{n}{2}\). We have already established that so long as \(m>\frac{n}{2}\), the extension and deletion maps form bijections between \(Puz (n,m)\) and \(Puz (n+l,m+l)\) for any \(l\in\mathbb{N}\). This results in the sequential stability displayed in the offdiagonals of Table 1. Now, we restrict our attention to the first time each stable value is achieved. Specifically, we devise a way to count \(Puz (2k-1,k)\) for all \(k\geq 1\). First we establish a bijective correspondence between \(Puz (2k-1,k)\) and \((k-1)\times(k-1)\) grids we call condensed void arrangements. In order to do so, we will focus on the voids in the northwest and northeast corners of the grid. As noted in Corollary 3.4, the inequality \(k\geq\frac{2k-1}{2}\) requires all voids to be path connected to a corner, and by the symmetry condition, the \(SW\) and \(SE\) voids are rotated copies of the \(NE\) and \(NW\) voids, respectively.
Since each row and column must contain an answer of length \(k\), the number of voids in each row or column may be at most \(k-1=(2k-1)-k\). So, we can consolidate these two regions and fit them on a \((k-1)\times(k-1)\) grid that we call the condensed void arrangement.
The 12 condensed void arrangements for \(d=2\) providing the 12 puzzles for \(n\geq5\) is shown in Figure 7 and a condensed void arrangement for the puzzle from Figure 4, and the corresponding path is shown in Figure 8.
Definition 5.1. For some \(k\in\mathbb{N}\), we consider a grid \(X\in Puz (2k-1,k)\). For \(X\) we construct the condensed void arrangement of \(X\), denoted \([X]\), as follows. Each square of an \((k-1)\times(k-1)\) grid is assigned a label. The label “\(NW\)” is attached to any square which is in the same position relative to the NW corner as a void from \(X\). The label “\(NE\)” is assigned in a similar fashion. The remaining squares are designated as cells.
First, let us establish that passing to the condensed void arrangement does not lose any information.
Theorem 5.2. For fixed \(k\), the map \([\,]\colon Puz (2k-1,k)\to Grid (k-1)\) is injective.
Proof. Suppose to the contrary that there exist two elements \(X_1,X_2\in Puz (2k-1,k)\) such that \(X_1\neq X_2\) but \([X_1]=[X_2]\). Since \(X_1\neq X_2\), then at least one of the void components in \(X_1\) is different from the similar labeled void component in \(X_2\). Without loss of generality, assume it is the northwest corner; that is, \(NW_1\neq NW_2\) where \(NW_1\) is the northwest void component of \(X_1\) and likewise for the other. Then relative to the northwest corner, there exists a square in \(X_1\) that is different from the corresponding square in \(X_2\), in that one puzzle contains a void and one puzzle contains a cell in that spot. Then, upon applying \([\,]\), the corresponding labels are different in that location, so \([X_1]\neq[X_2]\), a contradiction. ◻
Definition 5.3. Define the set \([ Puz (2k-1,k)]\subseteq Grid (k-1)\) to be set of condensed void arrangements of size (k-1).
Two distinct condensed void arrangements when \(d=4\) is shown in Figure 8.
This captures all possible void arrangement resulting from \((2k-1)\times(2k-1)\) crossword puzzles with minimum answer length \(k\) in their condensed form. A direct result of Theorem 5.2 is our next bijection.
Corollary 5.4. The map \([\,]\colon Puz (2k-1,k)\to[ Puz (2k-1,k)]\) is a bijection.
In the previous section we established a bijection between the set of crossword puzzle grids \(Puz (2k-1,k)\) and the set of condensed void arrangements \([ Puz (2k-1,k)]\). We now form a bijection between the set of condensed void arrangements and strings of the symbols \(\uparrow, \downarrow, \to\) of length \(3(k-1)\) satisfying specific conditions. First, let us note that the condensed void arrangement retains certain structure rules from our previous results. Two distinct condensed void arrangements when \(d=4\) are given in Figure 9.
Lemma 6.1. A \((k-1)\times(k-1)\) grid with squares labeled “\(NW\)”, “\(NE\)” or “cell” is \([X]\) for some \(X\in Puz (2k-1,k)\) if and only if the following conditions hold:
(1) in any row when going west to east the voids labeled \(NW\) must occur prior to any cells, which must occur prior to any voids labeled \(NE\)
(2) in any column, voids may not occur below cells.
(3) in any column, there cannot be voids from both \(NW\) and \(NE\)
(4) in any row the components \(NW\) and \(NE\), together, contain at most \(k-1\) voids
(5) the number of voids labeled \(NW\) in the westernmost column and the number of voids labeled \(NE\) in the easternmost column must add up to less than or equal \(k-1\).
Proof. Suppose \(X\in Puz (2k-1,k)\), then by Lemma 3.6, all of these conditions must follow for \([X]\).
For the other direction, suppose we have a grid in \(Grid (k-1)\) with labeling satisfying the conditions above. Generate a grid \(X\) of size \(2k-1\) from the void components \(NW\) and \(NE\). We claim \(X\in Puz (2k-1,k)\). Symmetry is satisfied since we generate all voids based on the two given components. By Conditions 5 and 4, the resulting grid \(X\) contains in each row/column at most \(k-1\) voids, and by Conditions 1 and 2, any void must be path connected (by voids) to its closest pair of edges. Thus, each row/column must contain a set of horizontally/vertically adjacent cells with length at least \(k\), and the must be the only set of cells in that given row/column. Therefore, the word length and keyed conditions are satisfied. Since our grid is odd dimension, there is a center row and a center column. Since the voids in each row/column comprise less than half, the center row and center column of \(X\) must be entirely cells, which guarantees full dimension. Conditions 1, 2, and 3 guarantee any cell in \(X\) is path connected by cells to the center row/column, providing connectivity. Thus, all conditions are met and \(X\in Puz (2k-1,k)\). ◻
We now turn our attention to an object we call the path of a condensed void arrangement.
Definition 6.2. An element of \(Grid (n)\) is a bounded subset of the integer lattice \(\mathbb{Z}^2\), and we can consider the SW corner as the cartesian coordinate \((0,0)\) and the NE corner as the cartesian coordinate \((n,n)\). We set \(s_0=(0,0)\) as the starting point. A step is a vector in \(\mathbb{Z}^2\), and for our purposes we will be restricting to the vertical steps \((0,1)\) and \((0,-1)\), as well as a single possible horizontal step \((1,0)\). The symbols \(\uparrow\), \(\downarrow\), and \(\to\) are used to denote lattice steps \((0,1)\), \((0,-1)\), and \((1,0)\), respectively. A lattice path in \(Grid (n)\) is a sequence of steps \((s_1,s_2,…,s_j)\) such that \(\sum\limits_{i=0}^l s_i\) remains in \(Grid (n)\) for all \(0\leq l\leq j\). We use the word \(w=s_1s_2…s_j\) to denote the corresponding path \((s_1,s_2,…,s_j)\). The symbol \(\epsilon\) is used to denote the empty word, and \(\oplus\) to denote a concatenation of words. For any step \(s_i\) and word \(w\), we denote by \(\#(s_i,w)\) the number of steps \(s_i\) which occur in the word \(w\).
Lemma 6.3. For \([X]\in[ Puz (2k-1,k)]\), there exists a unique lattice path of length \(3(k-1)\) with steps \((1,0)\), \((0,1)\), and \((-1,0)\) which
(1) starts at \((0,0)\)
(2) reaches a height of \(k-1\)
(3) ends at \((k-1,0)\)
(4) divides \([X]\) into three connected components: the cells, the voids in \(NW\), and the voids in \(NE\)
(5) does not go below any cell
(6) stays to the right of any void from NW
(7) stays to the left of any void from NE
Proof. First, we construct such a path. Let \([X]\in[ Puz (2k-1,k)]\). The condensed void arrangement \([X]\) is a \((k-1)\times(k-1)\) grid, and we may consider the southwest corner as the cartesian coordinate \((0,0)\) and the northeast corner as \((k-1,k-1)\). We algorithmically construct a path which satisfies our necessary conditions using Algorithm 1. At each step, our path will terminate at a particular coordinate \((x,y)\). Depending on the phase of our construction we are in, our next step might depend on the next up square, which has \((x,y)\) as its southwest corner, or the next down square, which has \((x,y)\) as its northwest corner. In Phase 1, the path connects from \((0,0)\) to a height of \(k-1\), while separating any NW voids from any cells. In Phase 2, the path continues to the eastern edge of the grid while separating any NE voids from any cells. In Phase 3, the path continues along the eastern edge to \((k-1,0)\). In each phase, the path stays above any cells, to the right of any voids from \(NW\), and to the left of any void from \(NE\). We call this path \(w([X])\). Next, we establish uniqueness. Suppose that another path \(w'([X])\) satisfies the same conditions. If there exists an edge of a square that is traversed by \(w([X])\) but not by \(w'([X])\), then the two paths break \([X]\) into distinct connected components, breaking (4). So, \(w([X])\) and \(w'([X])\) must traverse exactly the same edges of squares, and hence visit exactly the same coordinates. The only way for distinct paths to traverse the same edges and visit the same coordinates but be distinct is to have different lengths. This is a contradiction since both are assumed to have length \(3(k-1)\). ◻
Lemma 6.4. The map from \([ Puz (2k-1,k)]\) to words of length \(3(k-1)\) with symbols \(\{\uparrow,\downarrow,\to\}\) is injective.
Proof. Suppose two condensed void arrangements result in the same word. Then, they have the same path. The last four conditions of Lemma 6.3 dictates where voids and cells must occur in each row and column relative to the path. So the two condensed void arrangements must have had the same void components, and thus must be the same. ◻
Lemma 6.5. A word \(w\) of length \(3(k-1)\) on the symbol set \(\{\uparrow,\downarrow,\to\}\) is the path of some \([X]\in[ Puz (2k-1,k)]\) if and only if the following conditions hold:
(1) \(w\) is comprised of \(k-1\) of each symbol \(\uparrow,\downarrow,\to\)
(2) all \(\uparrow\) occur prior to the first \(\downarrow\)
(3) the number of \(\uparrow\) which occur before the first \(\to\) and the number of \(\downarrow\) which occur after the last \(\to\) add up to less than or equal to \(k-1\).
Proof. Suppose \(w=w([X])\) for some \([X]\in[ Puz (2k-1,k)]\). Then by Lemma 6.3, the corresponding path has length \(3(k-1)\), begins at \((0,0)\), reaches a height of \(k-1\), and ends at \((k-1,0)\). To complete this the path must have at least \(k-1\) of each of the steps \(\uparrow\), \(\downarrow\), and \(\to\), and thus must have exactly \(k-1\) of each, proving (1). Since there are \(k-1\) steps \(\uparrow\), the maximum height obtained is \(k-1\), and if any step \(\downarrow\) occurs prior to a \(\to\), then this value is decreased, which may not happen by Lemma 6.3. Thus, (2) holds. Condition (3) follows directly from the corresponding void conditions from Lemma 6.1 (5).
In the other direction, suppose we have a word of length \(3(k-1)\) satisfying (1), (2), and (3). Then we may apply the corresponding path to a \((k-1)\times(k-1)\) grid, starting at \((0,0)\). By (1) and (2), the path will reach a height of \(k-1\), and end at \((k-1,0)\). Label any squares that are west of an \(\uparrow\) with the label \(NW\). Label any squares that are east of a \(\downarrow\) with the label \(NE\). Label the remaining squares as cells. Such a labeling satisfies the first four necessary conditions of Lemma 6.1, and the fifth is guaranteed by (3). ◻
In order to complete the counting argument, we’ll use the fact that \(\binom{2d}{d}\) is even. The reader may use Pascal’s triangle or a straightforward proof to convince themselves of this, and upon further inspection, that \(\binom{2d}{d}=2\binom{2d-1}{d}\).
Lemma 6.6. The number of words of length \(3(k-1)\) on the symbol set \(\{\uparrow,\downarrow,\to\}\) resulting in a path of some \([X]\in[ Puz (2k-1,k)]\) is \[\binom{2(k-1)}{k-1}\frac{(k-1)}{2}+\binom{2(k-1)}{(k-1)}. \tag{1}\]
Proof. Let \([X]\in[ Puz (2k-1,k)]\) and consider \(w([X])\). We proceed by splitting into two cases. For the first case, suppose that \([X]\) includes some voids labeled \(NW\). Consider the number of \(\uparrow\) which occur before any other symbol in \(w([X])\), and call this number \(v\). We know \(v<k-2\), since the existence of a void in \(NW\) guarantees a \(\to\) before completing Phase 1 in Lemma 6.3. Since Lemma 6.5 places no further conditions on the number of initial \(\uparrow\), we have \(v\in\{0,1,\ldots,k-2\}\). Once this number has been determined, Lemma 6.5(3) requires at least \((k-1)-v\) of the symbol \(\downarrow\) at the end of \(w([X])\). So, in total, \(k-1\) of the verticals have been accounted for, as well as one horizontal (namely the \(\to\) that ends our initial run of \(\uparrow\)s). The remaining \(k-1\) verticals and \(k-2\) horizontals must be arranged. There are \(\binom{(k-1)+(k-2)}{k-1}\) ways to do so. Notice that \[\binom{(k-1)+(k-2)}{k-1}=\binom{2(k-1)-1}{k-1}=\frac{1}{2}\binom{2(k-1)}{(k-1)}. \tag{2}\]
Multiplying for the initial choice of \(v\), we get \(\frac{(k-1)}{2}\binom{2(k-1)}{(k-1)}\). For the second case, if there are no voids in \(NW\) then \(v=k-1\). What remains are \(k-1\) verticals and \(k-1\) horizontals which, by Lemma 6.5 can be arranged in any way, so there are \(\binom{2(k-1)}{(k-1)}\) possibilities. Combining the count from both of the cases, we get \[\frac{(k-1)}{2}\binom{2(k-1)}{k-1}+\binom{2(k-1)}{}. \tag{3}\] ◻
We’ll now prove our main result: a formula to count \(\lvert Puz (n,m)\rvert\) for \(m>\frac{n}{2}\).
Theorem 6.7. Consider an \(n\times n\) crossword puzzle grid and say that we have minimum word length of \(m\). Let \(d=n-m\). Then if \(m>\frac{n}{2}\), then there are \(\binom{2d}{d}\frac{d}{2}+\binom{2d}{d}\) possible crossword puzzle grids. That is, \[\begin{aligned} \lvert Puz (n,m)\rvert &= \binom{2(n-m)}{(n-m)}\frac{(n-m)}{2}+\binom{2(n-m)}{(n-m)}\\ &= \binom{2d}{d}\frac{d}{2}+\binom{2d}{d}. \end{aligned}\]
Proof. Suppose \(m>\frac{n}{2}\). Then by Theorem 4.6, we may pass to the first stable entry and have \(\lvert Puz (n,m)\rvert=\lvert Puz (2k-1,k)\rvert\) for \(k-1=n-m\). By Corollary 5.4, we may pass to the condensed void arrangement and have \(\lvert Puz (2k-1,k)\rvert=\lvert[ Puz (2k-1,k)]\rvert\). By Lemma 6.5, we may count \(\lvert[ Puz (2k-1,k)]\rvert\) by counting the corresponding paths. Thus, letting \(d=n-m=k-1\) and invoking Lemma 6.6, we see \[\begin{aligned} \lvert Puz (n,m)\rvert &= \frac{(k-1)}{2}\binom{2(k-1)}{k-1}+\binom{2(k-1)}{(k-1)}\\ &= \binom{2(n-m)}{(n-m)}\frac{(n-m)}{2}+\binom{2(n-m)}{(n-m)}\\ &= \binom{2d}{d}\frac{d}{2}+\binom{2d}{d} \end{aligned}\] ◻
The sequence of integers formed by \(\binom{2d}{d}\frac{d}{2}+\binom{2d}{d}\) is OEIS sequence A092443, which begins: \(3,12,50,210,882,3696,15444,64350,267410,1108536,4585308,18929092,\ldots\) These are stable subdiagonal values we see in Table 2 for \(d=1,2,3,4,\ldots\).
| Minimum answer length \(m\) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 11 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 47 | 10 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | ? | 57 | 12 | 3 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | ? | ? | 48 | 12 | 3 | 1 | 0 | 0 | 0 | 0 |
| 7 | ? | ? | 312 | 50 | 12 | 3 | 1 | 0 | 0 | 0 |
| 8 | ? | ? | ? | 208 | 50 | 12 | 3 | 1 | 0 | 0 |
| 9 | ? | ? | ? | ? | 210 | 50 | 12 | 3 | 1 | 0 |
| 10 | ? | ? | ? | ? | 880 | 210 | 50 | 12 | 3 | 1 |
| 11 | ? | ? | ? | ? | ? | 882 | 210 | 50 | 12 | 3 |
While the results for \(m>n/2\) provide a closed-form solution for the upper-right portion of our table, other grid dimensions often present unique structural interactions that the general formula does not capture. In these cases, the “buffer zone” of center cells is either reduced or absent, requiring a more systematic enumeration to account for the emergence of interior voids and specific boundary constraints. In this section, we present two such proofs.
Theorem 7.1. \(\lvert Puz (4,1)\rvert=47\)
Proof. We will proceed to count all \(4\times 4\) crossword puzzle grids with no minimum word length requirement. In order to do so, we break into two cases. For the first case, we will count the grids in which all voids are along the boundary. For the second case, we will count the grids in which some void is not along the boundary.
Case 1: Suppose all the voids in the grid appear along the boundary. We proceed by counting the complement. Due to symmetry, we can focus on how many voids are in the upper half of the boundary and eliminate grids that break the connectivity or full-dimension rules. Notably, if all voids are along the boundary then the only way to break connectivity is to isolate a corner cell and the only way to break full-dimension is to void an entire row or column. In Table 3, we count the possible ways to have \(V\) voids in the upper half of the boundary, and list the arrangements which break connectivity or full dimension. Subtracting these, we conclude there are 42 allowable \(4\times 4\) grids with no minimum word length where all voids are along the boundary.
Case 2: Suppose there exist voids which are not along the boundary. We can focus again on the upper half, and count the possible ways to add successive voids. In Figure 10, we show all 5 possible arrangements.
Combining the two cases, we find \(\lvert Puz (4,1)\rvert=47\). ◻
Theorem 7.2. \(\lvert Puz (5,2)\rvert=57\)
Proof. Here we will restrict our attention to the fundamental region (FR), namely the top two rows and the center row up to and including the center square. The remainder of the puzzle is determined by the symmetry condition. On a fundamental region, we cross out the center square if voiding that square would break answer length or connectivity.
First we consider puzzles without any corner voids. If no corners are voided, then any voids must be in the center or in the center of an edge. In Figure 11, we see the five possible puzzles.
Now, suppose that there is at least one void in a corner. Puzzles with only one corner void in the fundamental domain may be split into two equal sets based on if the upper right or upper left corner is voided. Due to this, we will list the upper left and then double count to allow for their reflected counterparts.
Table 4 lists all puzzles with a void in the upper left corner. There are 13 with only one corner void, four of which allow for a center void. Taking that 17 and doubling to account for reflected counterparts we get 34. There are 9 with two corner voids, all of which allow for a center void, making 18. This brings us to 52. Adding in the 5 with no corner voids from Figure 11, we arrive at 57. ◻
We are now able to present an updated table, where bold values are results from above.
In this paper, we have defined and explored the enumerative combinatorics of American-style crossword grids under varying answer-length requirements. We have demonstrated that when the minimum answer length \(m\) is greater than half the grid dimension \(n\), the total number of valid grids \(\lvert Puz (n,m)\rvert\) becomes stable for a fixed difference \(d=n-m\). Our analysis established a closed-form formula, \(\lvert Puz (n,m)\rvert=\binom{2d}{d}\frac{d}{2}+\binom{2d}{d}\), which links these stable counts to the OEIS sequence A092443. Alongside these structural theorems, we have provided systematic counts for smaller dimensions where interior and boundary voids play a more complex role, specifically establishing that \(\lvert Puz (4,1)\rvert=47\) and \(\lvert Puz (5,2)\rvert=57\). We also verified the transition point for even dimensions, proving that the count immediately prior to stabilization follows the relationship \(\lvert Puz (n,m)\rvert=\lvert Puz (n+1,m+1)\rvert-2\). While we have fully characterized the upper-right region of Table 2, the lower-left region where \(m\leq n/2\) remains a rich area for future study.
