3 ms·

in a sufficiently compact language crosswords are impossible as well, but now because puzzles would be ambiguous: too many words that fit This ignores

by cbr 13y ago

in a sufficiently compact language crosswords are impossible as well, but now because puzzles would be ambiguous: too many words that fit This ignores the clues, which restrict which words are acceptable in a space. While the clues are mostly there to make the puzzle easier, resolving ambiguity is a secondary purpose.

cscheid 13y ago
So I looked it up, and it's actually on the seminal 1948 paper: http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd... It turns out that I either hallucinated (incorrectly, perhaps) one side of the argument, or I read it from some other place, because the paper only talks about one side, the one about feasibility. The relevant paragraph follows: "The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc." Anyway, to somewhat rescue a botched story, the ambiguity part reminds me of the mindblowingly awesome and famous puzzle by Jeremiah Ferrell on the eve of the 1996 presidential election, which clue was "Lead story in tomorrow's paper", with possible answers BOBDOLE ELECTED or CLINTON ELECTED, both satisfying all crossclues as well! Amazing: http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/nytimescrossword.jpg http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/...

by cbr 13y ago

cscheid 13y ago

So I looked it up, and it's actually on the seminal 1948 paper: http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd... It turns out that I either hallucinated (incorrectly, perhaps) one side of the argument, or I read it from some other place, because the paper only talks about one side, the one about feasibility. The relevant paragraph follows: "The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc." Anyway, to somewhat rescue a botched story, the ambiguity part reminds me of the mindblowingly awesome and famous puzzle by Jeremiah Ferrell on the eve of the 1996 presidential election, which clue was "Lead story in tomorrow's paper", with possible answers BOBDOLE ELECTED or CLINTON ELECTED, both satisfying all crossclues as well! Amazing: http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/nytimescrossword.jpg http://cdn0.dailydot.com/uploaded/images/original/2013/2/12/...