OFFSET
1,3
COMMENTS
Uses New York Times rules of: connectivity, 180-degree 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
Kevin K. Ferland, Record crossword puzzles, The American Mathematical Monthly, 121 (2014), 534-536.
Kevin K. Ferland, Proof of Crossword Puzzle Record
Kevin K. Ferland, Counting Clues in Crosswords, Recreational Mathematics Magazine, (2020) Vol. 7, Issue 13, 1-7.
Rob Pratt, Illustrations of solutions for n <= 50
FORMULA
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.
EXAMPLE
The trivial all-white puzzle is optimal for 3 <= n <= 6.
The Ferland paper shows that a(15) = 96.
CROSSREFS
KEYWORD
nonn
AUTHOR
Rob Pratt, Jun 11 2014
EXTENSIONS
STATUS
approved