[math-fun] How Many Crossword Puzzles Are There?
My friend Bob Baillie <rjbaillie@frii.com> asks
Has anyone ever estimated how many crossword puzzles of size N by N there are, where the entries are words in English?
I assume that the answer for very large N must be exponential in the area of the crossword. Assume we can make two KxK tiles with the same boundary conditions but differeing internally, and that all the necessary fixups can be made on the outer edge of the pattern. Similar questions could be asked for a randomly generated language with English statistics, and for other real languages. But this is not really the question he's asking. Rich
My significant other <rcs@CS.Arizona.EDU> notes that
My friend Bob Baillie <rjbaillie@frii.com> asks
Has anyone ever estimated how many crossword puzzles of size N by N there are, where the entries are words in English?
It depends on the rules. For example, very few real crossword puzzles limit themselves to English words. The most important question, though, is whether or not single letters are permitted, as in "Roman 5" or "letter trilled in Spanish" or "13th in the alphabet". If single letters are allowed, then I'd guess that there are about 10^16 basic word blocks, and it would seem that they could be patched together almost arbitrarily using little "glue" words. Hilarie
participants (2)
-
Richard Schroeppel -
The Purple Streak, Hilarie Orman