How Far Away Are Computer-Generated Crosswords?

[Image courtesy of ESLTower.]

There’s no denying that computers play a large role in the world of crosswords today.

Some companies use computer programs to generate their unthemed crosswords, no human intervention necessary. Computer programs like Crossword Compiler aid constructors in puzzle design and grid fill, allowing them to build and cultivate databases of words with which to complete their grids.

And, of course, with those little computers in your pocket, you can solve all kinds of crosswords (like those in our Daily POP Crosswords and Penny Dell Crosswords apps).

Heck, computers are even getting pretty good at solving crosswords — just look at Matt Ginsberg’s evolving crossword program, “Dr. Fill.

An article in Smithsonian Magazine posed the question, “why haven’t computers replaced humans in crossword creation?”

The answer, as you’d expect, is simple: computers are just fine at plugging words into established grids and generating basic, unthemed crosswords.

But unthemed is the key word there.

When people think of The Los Angeles Times, The New York Times, The Chronicle of Higher Education, The American Values Club, The Crosswords Club, or any of the other well-respected crossword outlets in the market today, I doubt unthemed puzzles are what comes to mind.

And when it comes to creating themes, innovating, and playing with the conventions of crosswords in order to create puzzles that surprise and challenge solvers, computers simply don’t have the chops.

They might be able to solve puzzles, but as far as I can tell from my research, there’s no program out there capable of generating and executing a theme with any sort of wordplay element involved.

[Image courtesy of Crossword Compiler.]

There is an art to creating an exciting grid, an intriguing theme, or a new puzzle mechanic that solvers have never seen before. The creativity of constructors is truly boundless.

And, it seems, the potential for crossword grids is just as boundless.

Recently, Oliver Roeder of FiveThirtyEight challenged the puzzle fans in his readership to calculate how many different crossword puzzle grids were possible.

He offered the following conditions:

  • They are 15-by-15.
  • They are rotationally symmetric — that is, if you turn the grid upside down it appears exactly the same.
  • 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.
  • The grid must be entirely connected — that is, there can be no “islands” of white squares separated from the rest by black squares.

Now, obviously, all of those rules can be violated for the sake of an interesting theme. We’ve seen grids with vertical symmetry, islands of white squares, and more. Heck, plenty of grids allow words to go beyond the grid itself, or allow multiple words to share puzzle squares.

[“Cutting Edge” by Evan Birnholz. A puzzle where answers extend
beyond the grid. Image courtesy of The Washington Post.]

But assuming these rules are standard, what total did solvers come up with?

None. They couldn’t find a total.

One solver managed to calculate that there were 40,575,832,476 valid 13-by-13 grids following the above conditions, but could not apply the same technique to 15-by-15 grids.

40 billion valid grids. For a comparison, there are 5,472,730,538 unique solutions for a 9×9 Sudoku grid, and I previously calculated it would take 800 years to use every possible 9×9 Sudoku grid.

Of course, that’s 40 billion 13-by-13 grids. The number of possible 15-by-15 grids must be orders of magnitude larger.

Consider this: There were 16,225 puzzles published in The New York Times before Will Shortz took over the NYT crossword. The current number of NYT crosswords in the XWordInfo database is somewhere in the neighborhood of 25,000 puzzles.

And they’re one of the oldest crossword outlets in the world. Even when you factor in the number of newspapers, magazines, subscription services, and independent outlets for crosswords there are these days, or have been in the past, we barely scratch the surface of a number like 40 billion.

Maybe by the time we’ve run through that many, AI constructors will have caught up.


Thanks for visiting PuzzleNation Blog today! Be sure to sign up for our newsletter to stay up-to-date on everything PuzzleNation!

You can also share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and explore the always-expanding library of PuzzleNation apps and games on our website!

3 thoughts on “How Far Away Are Computer-Generated Crosswords?

  1. hi
    i’ve been mining the solution space for 5×5 crosswords with no blanks.
    USING A LIST OF 5757 5-LETTER WORDS
    solution space to explore:
    5757 * 5757 * 5757 * 5757 * 5757 = 6,323,843,989,723,420,557
    this would be serious supercomputer time
    but there are tricks to reducing the search space.
    i may be able to do this job in @ 34 years with one computer now
    🙂

    i have a nice twist in mind for these puzzles – a symmetrical array of circles in the grid boxes designate the letters of an anagram that’s the punch line for a funny clue.

    after a lot of coding and processing time- i woke up today to find 70 valid 5X5 puzzles!
    this was an unexpected thrill – so i intend to keep chomping the data

    i’d be delighted to find somebody interested in helping to create the ‘Cross-Wits’ puzzles from 5X5 puzzles i can provide.

    anybody out there?

    • You might have luck matching up with someone on Twitter or in the Facebook group about crossword collaboration.

  2. Pingback: And… Repeat | PuzzleNation.com Blog

Leave a Reply to gmdirect Cancel 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