Count of NxN American-style crossword grids

[Arthur O'Dwyer]

Motivated by Malaika Handa's "7xwords" project https://www.7xwords.com/why.html —

By her count there were 312 seven-by-seven valid American-style crossword grids.

An American-style crossword grid must have:

- Rotational symmetry

- No "unchecked" white cells: every letter belongs to entries in both directions

- No 2-letter entries

- No full rows or columns of black at the edges (that would just make the grid a smaller rectangle)

- All white cells kingwise connected (no isolated "islands" of white)

If you consider

#....

#....

.....

....#

....#

to be the same grid as

##...

.....

.....

.....

...##

(because it just swaps the Across and Down entries, without changing any of the topology of the grid) then according to my dumb computer search (which might be wrong), there are this many valid grids of size 3x3, 4x4, etc.:

3 1

4 3

5 10

6 33

7 193

8 1224

If you consider those two grids distinct (as Malaika Handa did: [1] [2]), then there are this many:

3 1

4 3

5 12

6 48

7 312

8 2190

Neither of these sequences is in the OEIS, as far as I can tell. I'm not sure they should be ("American crossword rules" is pretty arbitrary), but I thought it was interesting enough for a post to SeqFans, at least.

An even more interesting sequence might be the number of valid grids without "cheaters" (black cells bordered on two consecutive sides by other black cells, such that whitening them would increase the crossword's average entry length without increasing the number of entries). According to my computer, that sequence begins

3 1

4 1

5 1

6 1

7 7

8 32

9 177

or by Malaika's method

3 1

4 1

5 1

6 1

7 10

8 55

9 322

Cheers,

Arthur

[Arthur O'Dwyer]

...As usual, clicking "Send" worked to find me more information instantly. :)

https://oeis.org/A323839 is "1, 12, 312, 31187," which is just the odd elements of one of the sequences I suggested.

The question of enumerating grids, and even cheater-less grids, was the subject of the 2019-01-18 "The Riddler" puzzle on the now-defunct FiveThirtyEight.com. (And a partial answer in 2019-01-25's column.)

A really impressive solution to that puzzle by Jim Ferry is here (with many pretty pictures in the slide deck).

Searching for the 15x15 Riddler answer, "404,139,015,237,875," turns up many people's forays in this area, e.g.

- https://www.georgeho.org/counting-cryptics/

So I guess I'm very late to that party, and relatively empty-handed!

–Arthur