6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Do words in the same row/column need to be separated by a shaded square? $\endgroup$
    – hexomino
    Jul 4, 2020 at 21:42
  • $\begingroup$ @hexomino: How else would "word spaces" be delimited? $\endgroup$ Jul 4, 2020 at 21:56
  • 3
    $\begingroup$ @DanielMathias Possibly with horizontal/vertical bars, see for example this style: puzzling.stackexchange.com/questions/99641/… $\endgroup$
    – hexomino
    Jul 4, 2020 at 21:58

1 Answer 1

13
$\begingroup$

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 ≤ 50PDF 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}$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – humn
    Jul 7, 2020 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.