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$
  • 1
    $\begingroup$ Do words in the same row/column need to be separated by a shaded square? $\endgroup$ – hexomino Jul 4 at 21:42
  • $\begingroup$ @hexomino: How else would "word spaces" be delimited? $\endgroup$ – Daniel Mathias Jul 4 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 at 21:58
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}$$

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for adding this, @humn $\endgroup$ – RobPratt Jul 7 at 2:01
  • $\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 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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