HI all! Reviving this crossword puzzle thread from February. So the original "538 Riddler" problem asked about counting 15x15 crossword puzzle grids, since that's the standard weekday NYT puzzle size, and also offered "extra credit" [*] for counting the 21x21's. After I did the 15x15 with a little python program running on my own computer, I decided I should be a Real Googler and wrap it up into an Apache Beam Python program to let me run it in The Cloud(tm), so that I could have thousands of computers counting equivalence classes of crossword puzzle grids instead. Wasting computers' time has become so much more efficient since I was in grad school! That made it straightforward to ramp up the calculation to 17x17 and even 19x19. For 21x21 to be practical, I needed a few rounds of efficiency improvements -- basically four different changes that each cut the CPU time and/or temporary data storage needs in half. One of those necessary changes turned out to be a baby version of Dan's suggestion! I had been keeping track of all the crossword grids, which meant that I was tracking each grid and its left-right mirror image, doubling the number of (equivalence classes of) grids I needed to compute on and store. This required a little effort to avoid, since you can't just cut everything in half -- you need to correctly account for the puzzles which are their own mirror image. So my equivalence-class definition expanded to include an "is this grid symmetric?" bit, which means in the end I could count the subset of rot180-symmetric grids that actually had (both left-right and up-down) mirror symmetry. This, along with an embarrassment of my employer's available computational resource riches, was enough to get 21x21 just barely in reach; anything larger would be right out. Results, for n=3,5,7,9,11,13,15, and now 17,19,21 as well: Crossword grids "up to nxn", i.e. allowing all-black outside rows/columns: 1, 15, 397, 35324, 18446134, 41752489852, 409764131469787, 17368974525101032256, 3195393813996265512672344, 2544868518166378264304163732974 Crossword grids "fully nxn", i.e. white squares reach all edges of the grid: 1, 12, 312, 31187, 17438702, 40575832476, 404139015237875, 17253201646564115439, 3185118492387669085270268, 2540927098290913247876202007100 Crossword grids "up to nxn" and with orthogonal Z2 x Z2 symmetry: 1, 5, 35, 436, 11348, 650798, 78816939, 19500572516, 10050221059942, 10777659213636406 Crossword grids "fully nxn" and with orthogonal Z2 x Z2 symmetry: 1, 2, 20, 269, 8116, 519400, 67566361, 17518353991, 9334778743018, 10240638005472594 (Yes, I've proposed edits to A323838 and A323839, and added the two new with-symmetry sequences as A325408 and A325409.) [*]: Of course getting "extra credit" for 21x21 would require getting any credit at all; that Roeder guy never mentioned my solution to his puzzle! --Michael On Wed, Feb 6, 2019 at 9:36 AM Michael Kleber <michael.kleber@gmail.com> wrote:
Ugh -- turns out I had a bug in the program, as revealed by a Twitter correspondent who fortunately did independent counting for 9x9. For the record, the correct values are:
All grids: 1, 15, 397, 35324, 18446134, 41752489852, 409764131469787 No black edges: 1, 12, 312, 31187, 17438702, 40575832476, 404139015237875
Apologies, Neil; I've proposed edits for A323838 and A323839.
Dan: Hmm, I don't immediately see how I would count the rot90-symmetric grids, now that you mention it...
--Michael
On Mon, Feb 4, 2019 at 1:59 PM Dan Asimov <dasimov@earthlink.net> wrote:
Nice!
Now let's find the counts for the grids that *also* have symmetry group G, for each subgroup G of Isom([0,1]x[0,1]) = D_4, the dihedral group of order 8.
(There are 10 subgroups altogether: the trivial group, the whole group, and 5 isomorphic to Z_2, 1 to Z_4, 2 to Z_2 + Z_2.)
—Dan
----- The 538 Riddler from two and a half weeks ago asked for the number of 15x15 black-and-white grids that are legal for crossword puzzles.
https://fivethirtyeight.com/features/how-many-crossword-puzzles-can-you-make...
Rules: Every white square must be "checked" (in both a horizontal and vertical word), words must be at least 3 letters long, the whole grid must be symmetric under 180-degree rotation, and the set of white squares must be connected.
Evidently nobody solved it, so I decided to :-)
Answer: there are 347804238364806 legal 15x15 grids according to those rules (347 trillion). And if you don't like the fact that those rules allow some all-black rows around the edges of the puzzle, and want them to be "really" 15x15, then that cuts down the count to 342935406100702.
To convey the information to the outside world (including the 538 Riddler guy), I've posted some more about this on Twitter. Please forgive me.
https://twitter.com/Log3overLog2/status/1092472516571000839
NJAS, the sequence of counts of nxn grids for n=3,5,7,9,11,13,15 is: All grids: 1, 15, 397, 35184, 17431781, 37147554097, 347804238364806 No black edges: 1, 12, 312, 31047, 16459558, 36076951460, 342935406100702 -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.