%I #54 Dec 29 2020 20:40:23

%S 0,0,6,8,10,12,22,28,32,40,50,64,72,84,96,116,126,144,158,184,198,220,

%T 236,268,284,312,332,368,388,420,442,484,506,544,570,616,642,684,712,

%U 764,792,840,872,928,960,1012,1046,1108,1142,1200

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

%C Uses New York Times rules of: connectivity, 180-degree rotational symmetry, answer length at least 3.

%C a(1)-a(50) computed by using integer linear programming.

%C 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).

%H Kevin K. Ferland, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.121.06.534">Record crossword puzzles</a>, The American Mathematical Monthly, 121 (2014), 534-536.

%H Kevin K. Ferland, <a href="https://www.maa.org/sites/default/files/pdf/pubs/amm_supplements/RecordXwordsProof.pdf">Proof of Crossword Puzzle Record</a>

%H Kevin K. Ferland, <a href="https://doi.org/10.2478/rmm-2020-0001">Counting Clues in Crosswords</a>, Recreational Mathematics Magazine, (2020) Vol. 7, Issue 13, 1-7.

%H Rob Pratt, <a href="/A243826/a243826_1.pdf">Illustrations of solutions for n <= 50</a>

%F Except for n = 7, 11, and 19, conjectured recursive formula is a(n) = a(n-4) + 4(n-3) - [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.

%e The trivial all-white puzzle is optimal for 3 <= n <= 6.

%e The Ferland paper shows that a(15) = 96.

%K nonn

%O 1,3

%A _Rob Pratt_, Jun 11 2014

%E Upper bound and conjectured formulas from _Rob Pratt_, Jun 23 2014

%E More terms from _Rob Pratt_, Jul 06 2015