A Solution for the Ten Letter Acrostic Puzzle?
rmo101 asks: "A story in the Times reports a solution to the ten letter acrostic square puzzle that has defied solution since the ancient Greeks. An acrostic puzzle comprises a square of letters where the arrangement of letters from words written in rows result in the same words appearing vertically in the same order. The ten letter solution, however, is not accepted by all as one of the words does not appear in a dictionary. Sounds like a puzzle in search of a fiendish algorithm for interrogating a dictionary. The ancient Greeks believed that the solver of the ten letter puzzle would become immortal. Anyone fancy their chances?" Of course, the Times article doesn't report the proposed ten-letter solution (they show a five-letter one), but they do mention the controversial word: "nonesevent". Are any of you interested in trying your hand at a better solution?
One which stuck in mind goes as follows:
ALLUP
LEIRU
LIGIL
URIEL
PULLA
When ritually consecrated they are said to be capable of producing magic effects; at least according to the mystics.
Before enlightenment - Code C, read Usenet, play NetHack. After enlightenment - Code C, read Usenet, play NetHack.
Reminds me of a bit of Hofstader's Metamagical Themas:
Only the fool would take trouble to verify that his sentence was composed of ten a's, three b's, four c's, four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens and, last but not least, a single !
There's got to be a piece of math that finds the positions where all constraints are satisfied as in the above quote.
Shh.
Benjamin Zimmer over at Language Log notes some problems with the story. Most notably:
There's no evidence that the composition of word squares, let alone 10-squares, was a pastime in ancient Greece.
And, there's the timeliness of the article:
[I]t's unclear why the Times thought that this was at all newsworthy, considering that Clarke announced his discovery of the square back in April 1999, in an issue of his e-zine WordsWorth.
It's a sparseness problem. The space of two letter words is pretty full, but as the length of the words increases, the number of words does not increase as fast as the number of possible combinations.
I've actually written a program to generate the Dutch solutions to the 5x5 puzzle somewhere around 1990, and it found several good solutions with a 210,000 word dictionary. However, it didn't find solutions for the 6x6 square. So I would expect that the 10x10 square is near impossible, unless wacky compounds would be allowed, since they are the only thing that can keep the letter combination filled...