Creating Crossword Grids

Another week, another riddler. This week’s puzzle:

 

Crossword puzzle grids typically obey a few rules and conventions.

  1. They are 15-by-15.
  2. They are rotationally symmetric — that is, if you turn the grid upside down it appears exactly the same.
  3. All the words — that is, all the horizontal and vertical sequences of white squares — must be at least three letters long. All the letters must appear in an “across” word and a “down” word.
  4. The grid must be entirely connected — that is, there can be no “islands” of white squares separated from the rest by black squares.

First question: How many such crossword grids are there?

Second question: Crossword constructors do well to avoid using “cheater squares,” black squares whose addition makes some words shorter but does not change the puzzle’s total word count. How many grids are there without cheater squares?

Extra credit: The Sunday “New York Times” puzzle is 21-by-21. How many of those are there, with and without cheater squares?

 

So in short we didn’t make all of the grids — this turned out to be very difficult and I am very interested to see the approach that others used to tackle this problem. However we did make something that generated around a thousand of them

1234

 

Code can be found here

Advertisements

One thought on “Creating Crossword Grids

  1. Pingback: Time For Some Abstract Math. Drink Up.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s