

A243826


Maximum number of clues in a certain class of n X n crossword puzzles.


1



0, 0, 6, 8, 10, 12, 22, 28, 32, 40, 50, 64, 72, 84, 96, 116, 126, 144, 158, 184, 198, 220, 236, 268, 284, 312, 332, 368, 388, 420, 442, 484, 506, 544, 570, 616, 642, 684, 712, 764, 792, 840, 872, 928, 960, 1012, 1046, 1108, 1142, 1200
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Uses New York Times rules of: connectivity, 180degree rotational symmetry, answer length at least 3.
a(1)a(50) computed by using integer linear programming.
Because each row or column can have at most (n+1)/4 clues (consider appending a black square, and note that every clue requires 4 squares), we have a(n) <= 2n floor((n+1)/4).


LINKS

Table of n, a(n) for n=1..50.
Kevin K. Ferland, Record crossword puzzles, The American Mathematical Monthly, 121 (2014), 534536.
Kevin Ferland, Proof of Crossword Puzzle Record
Rob Pratt, Illustrations of solutions for n <= 50


FORMULA

Except for n = 7, 11, and 19, conjectured recursive formula is a(n) = a(n4) + 4(n3)  [2 if mod(n,8) in {1,7}]. In particular, conjectured explicit formula is a(n) = 2n floor((n+1)/4) if mod(n,4) = 2.


EXAMPLE

The trivial allwhite puzzle is optimal for 3 <= n <= 6.
The Ferland paper shows that a(15) = 96.
From Elizabeth Axoy, Aug 20 2019: (Start)
Here is a 15 X 15 crossword with 96 words, where 0 is a white square and 1 is a black square.
000010000100000
000010000100000
000010000100000
111000111000111
000001000010000
000100000001000
000010000100000
111000111000111
000001000010000
000100000001000
000010000100000
111000111000111
000001000010000
000001000010000
000001000010000
(End)


CROSSREFS

Sequence in context: A168335 A315852 A155776 * A295318 A184111 A181764
Adjacent sequences: A243823 A243824 A243825 * A243827 A243828 A243829


KEYWORD

nonn


AUTHOR

Rob Pratt, Jun 11 2014


EXTENSIONS

Upper bound and conjectured formulas from Rob Pratt, Jun 23 2014
More terms from Rob Pratt, Jul 06 2015


STATUS

approved



