6

What is the maximum number of "words spaces" that can be in an n×n crossword, based on the placement of the shaded squares.

Some limitations

  • No word can be less than 3 spaces in length
  • Every cell in the grid must be part of an across AND a down

For example, for a 3×3 grid, there are 6 maximum words (3 downs, 3 acrosses), because no shaded squares can be added without creating word spaces of less than length 3.

Any discussion helps. Thanks

msh210
  • 12,844
  • 2
  • 49
  • 120
ocuke
  • 63
  • 4

1 Answers1

13

Kevin Ferland and I have a paper on this: Maximal Crossword Grids, Journal of Combinatorial Mathematics and Combinatorial Computing (Feb. 2019)

See also OEIS A243826, which has a link to Ferland's earlier paper.

Here are a summary table and selected examples from Illustrations of solutions for 3 ≤ n ≤ 50 PDF at OEIS A243826.

$$ \small\begin{array}{rccc|rccc|rccc} n & \large{ W = \atop \textsf{words} } & 2n \left\lfloor{n+1 \over 4}\right\rfloor & W \over { 2n \left\lfloor{n+1 \over 4}\right\rfloor } & n & \large{ W = \atop \textsf{words} } & 2n \left\lfloor{n+1 \over 4}\right\rfloor & W \over { 2n \left\lfloor{n+1 \over 4}\right\rfloor } & n & \large{ W = \atop \textsf{words} } & 2n \left\lfloor{n+1 \over 4}\right\rfloor & W \over { 2n \left\lfloor{n+1 \over 4}\right\rfloor } \\ \hline 3 &\boldsymbol{ 6 }& 6 & 1 & 19 &\boldsymbol{ 158 }& 190 & .83 & 35 &\boldsymbol{ 570 }& 630 & .90 \\ 4 &\boldsymbol{ 8 }& 8 & 1 & 20 &\boldsymbol{ 184 }& 200 & .92 & 36 &\boldsymbol{ 616 }& 648 & .95 \\ 5 &\boldsymbol{ 10 }& 10 & 1 & 21 &\boldsymbol{ 198 }& 210 & .94 & 37 &\boldsymbol{ 642 }& 666 & .96 \\ 6 &\boldsymbol{ 12 }& 12 & 1 & 22 &\boldsymbol{ 220 }& 220 & 1 & 38 &\boldsymbol{ 684 }& 684 & 1 \\ 7 &\boldsymbol{ 22 }& 28 & .79 & 23 &\boldsymbol{ 236 }& 276 & .86 & 39 &\boldsymbol{ 712 }& 780 & .91 \\ 8 &\boldsymbol{ 28 }& 32 & .88 & 24 &\boldsymbol{ 268 }& 288 & .93 & 40 &\boldsymbol{ 764 }& 800 & .95 \\ 9 &\boldsymbol{ 32 }& 36 & .89 & 25 &\boldsymbol{ 284 }& 300 & .95 & 41 &\boldsymbol{ 792 }& 820 & .97 \\ 10 &\boldsymbol{ 40 }& 40 & 1 & 26 &\boldsymbol{ 312 }& 312 & 1 & 42 &\boldsymbol{ 840 }& 840 & 1 \\ 11 &\boldsymbol{ 50 }& 66 & .76 & 27 &\boldsymbol{ 332 }& 378 & .88 & 43 &\boldsymbol{ 872 }& 946 & .92 \\ 12 &\boldsymbol{ 64 }& 72 & .89 & 28 &\boldsymbol{ 368 }& 392 & .94 & 44 &\boldsymbol{ 928 }& 968 & .96 \\ 13 &\boldsymbol{ 72 }& 78 & .92 & 29 &\boldsymbol{ 388 }& 406 & .96 & 45 &\boldsymbol{ 960 }& 990 & .97 \\ 14 &\boldsymbol{ 84 }& 84 & 1 & 30 &\boldsymbol{ 420 }& 420 & 1 & 46 &\boldsymbol{ 1012 }& 1012 & 1 \\ 15 &\boldsymbol{ 96 }& 120 & .80 & 31 &\boldsymbol{ 442 }& 496 & .89 & 47 &\boldsymbol{ 1046 }& 1128 & .93 \\ 16 &\boldsymbol{ 116 }& 128 & .91 & 32 &\boldsymbol{ 484 }& 512 & .95 & 48 &\boldsymbol{ 1108 }& 1152 & .96 \\ 17 &\boldsymbol{ 126 }& 136 & .93 & 33 &\boldsymbol{ 506 }& 528 & .96 & 49 &\boldsymbol{ 1142 }& 1176 & .97 \\ 18 &\boldsymbol{ 144 }& 144 & 1 & 34 &\boldsymbol{ 544 }& 544 & 1 & 50 &\boldsymbol{ 1200 }& 1200 & 1 \\ \end{array}$$

RobPratt
  • 13,685
  • 1
  • 29
  • 56
  • Glad to append such a fascinating and handsome series of examples, @RobPratt. Your results are truly compelling. That optimality can be achieved for every 4th $n$ is very interesting. How the patterns behave along the edges of grids' quadrants is downright enjoyable. – humn Jul 07 '20 at 02:24