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!

A Relatively Modern Idea: Fairness in Dice Rolling

[Image courtesy of Larsdatter.com.]

This may come as a surprise to you, fellow puzzlers, but fairness was not always a priority when it came to rolling dice.

Nowadays, whether you’re going after that elusive Yahtzee, hoping for doubles to earn another roll in Monopoly, or trying to roll sevens in a game of craps, the basic concept behind throwing dice is that every outcome of a six-sided die has an equal chance to appear. Unless you’re dealing with loaded or gimmicked dice, your odds should be 1 in 6.

But a recent study by researchers from the American Museum of Natural History and the University of California, Davis, has revealed that fairness in dice rolling didn’t really become a concern for dice users until the Renaissance. Researchers gathered dice spanning 2000 years of human history to explore why this was the case.

[Image courtesy of Wikipedia.]

From an article on Science Alert:

Roman-era dice, the researchers found, were a mess when it came to shape. They were made from a variety of materials, such as metal, bone and clay, and no two were shaped entirely alike. Many were visibly lumpy and lopsided, with the 1 and 6 on opposite sides that were more likely to roll up.

In fact, it seems like variety was the name of the game in Roman times, since the number configurations, shape, and size were inconsistent across the board, although dice were fairly common in the time period.

[Image courtesy of Pinterest.]

The Dark Ages led to a downturn in dice frequency, as they become very rare between the years 400CE and 1100CE.

The use of dice rebounds after 1100, and are most commonly found in ancient Mesopotamia and Egypt in what is known as the primes configuration, meaning that opposite numbers add up to prime numbers. 1 pairs with 2, 3 pairs with 4, and 5 pairs with 6.

There was a reinvigorated focus on the mechanics of chance and calculating probability, thanks to names like Galileo and Pascal, as well as a spirit of greater scientific understanding overall. Those Renaissance influences led to both a standardized shape for dice and a change in the numbering system. At this point, most dice convert to the sevens configuration, where opposite sides add up to seven (1 pairs with 6, 2 pairs with 5, and 3 pairs with 4).

[Image courtesy of Smithsonian.com.]

And according to lead researcher Jelmer Eerkens, cheating may have been on the mind of manufacturers going forward. “Standardizing the attributes of a die, like symmetry and the arrangement of numbers, may have been one method to decrease the likelihood that an unscrupulous player had manipulated the dice to change the odds of a particular roll.”

That change from variable shapes, sizes, and designs reflects a sea change in thinking towards dice and chance. Before, the shape didn’t matter because the results were attributed to Fate or some greater outside force, but later on, an understanding of chance and probability pushed standardization of dice forward.

In the end, it’s amazing how much of our culture and worldview, both past and present, can be revealed by exploring how we solve puzzles and play games.


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!

These anagrams are out of this world!

Planets are in the news, as Pluto’s dubious planetary status is under the microscope once again.

Recently, a debate over the defining qualities of a planet was held at the Harvard-Smithsonian Center for Astrophysics, and three of the top names in planetary science presented their cases to the attending audience.

Now, although the audience overwhelmingly voted in favor of Pluto’s planethood, that’s not binding. This wasn’t an International Astronomical Union vote or anything like that.

But it did put the solar system back in the news cycle, and that reminded me of a puzzly planetary story.

In the 1600s, Galileo Galilei was doing amazing work with his telescope, redefining our understanding of the solar system and our place in it. He was doing controversial work, but he still wanted to be able to prove he was the primary person behind a given discovery, so he mailed a letter to his colleague, Johannes Kepler.

Galileo sent Kepler this anagram: s m a i s m r m i l m e p o e t a l e u m i b u n e n u g t t a u i r a s

When properly solved, the anagram reads “Altissimum planetam tergeminum observavi,” meaning “I have observed the most distant planet to have a triple form.” You see, Galileo had glimpsed Saturn and its famous rings, but due to the poor magnification of his telescope, he’d mistaken the rings themselves for two moons orbiting the planet.

This was a tremendous discovery, adding to our knowledge of what was (at the time) the furthest reaches of our solar system.

But Kepler, while trying to untangle the anagram, came to a different solution. Believing that Galileo’s latest discovery involved Mars, not Saturn, Kepler’s solution read “Salue umbistineum geminatum Martia proles,” meaning Mars has two moons. (The ambiguity of Latin V’s and U’s didn’t help matters.)

So, while Kepler was wrong in his solution, he was unintentionally correct about Mars! (Phobos and Deimos, the two moons of Mars, wouldn’t be confirmed until 1877.)

Amazingly enough, this wouldn’t be the only time Galileo relied on Kepler and anagrams to prove provenance when it came to his discoveries.

In 1611, Galileo sent another anagram to Kepler: Haec immatura a me iam frustra leguntur o.y.

Properly unscrambled, the message reads “Cynthiae figuras aemulatur mater amorum,” or “The mother of love imitates the shape of Cynthia.” This one requires a little more explanation. The mother of love was Venus, and Cynthia was the Moon, meaning that Venus, when observed from Earth, has phases just like the moon.

[Click here for a larger version of this image.]

This probably sounds less important than Galileo’s studies of Saturn, but it’s not. This was an earthshaking discovery, because it was observable evidence that Venus had to pass on both sides of the sun, meaning that Venus orbited the sun. This violated the geocentric model of the solar system so strongly espoused by the church!

It was evidence like this that led to Galileo’s battle with the Inquisition.

And, weirdly enough, there might be one more twist to this story.

Some historians believe that Kepler also solved this Galilean anagram incorrectly, and that his solution once again revealed an unintentional discovery about the solar system.

According to the as-yet-unverified story, Kepler’s solution read “Macula rufa in Jove est gyratur mathem…,” which translates as “There is a red spot in Jupiter, which rotates mathem[atically].” (Again, yes, there’s the Great Red Spot on Jupiter, but there was no way for Kepler to have known that at the time.)

It’s hard to believe that Kepler could twice unravel a Galileo anagram and twice make accidental predictions about the solar system. While the first story is widely accepted, the second is viewed with far more skepticism.

But either way, it just goes to show that anagrams, while delightful, might not be the best method for announcing your great discoveries.

Thanks for visiting PuzzleNation Blog today! You can share your pictures with us on Instagram, friend us on Facebook, check us out on TwitterPinterest, and Tumblr, and be sure to check out the growing library of PuzzleNation apps and games!