Word leader

from Wikipedia, the free encyclopedia

Word ladder is the name of a letter puzzle . The aim is to connect two given words of the same length by a chain of words by exchanging exactly one letter in each step. For example, HALM can be changed to KORN with the chain HALM - HALT - HART - HORT - HORN - KORN . In order to make the puzzle appealing, two words are often chosen, as in this example, which are also related in terms of content, i.e. are opposites or how one develops from the other here.

history

The riddle has been documented in writing since at least 1879. That year, Vanity Fair magazine published a series of puzzles of this type called Doublets , which Lewis Carroll had designed and provided with a set of rules for awarding points. In the same year the puzzles appeared in book form. Carroll writes that he had heard of an American game based on a similar principle, but developed the puzzle independently to entertain two girls at Christmas 1877.

In 1927, JE Surrick and LM Conant published a book called Laddergrams that contained such puzzles.

Theoretical investigation

The puzzle can be examined theoretically by looking at the graph in which the corners represent the words and an edge is drawn in if the corresponding words differ in exactly one letter. A connection can then be found for two words exactly when they are in the same connected component; the shortest connection can be determined with the Dijkstra algorithm .

One of the first analyzes of the resulting graph comes from Donald E. Knuth , who coined the term aloof (offside) in English for words that have no connection, aloof itself being an example of such a word.

The results of Erdős and Rényi on random graphs make it seem plausible that there is one large and several very small connected components, provided that the average number of connections of a word exceeds a certain critical value. This is the result of various studies of the graphs formed by English words of different lengths.

variants

Instead of only allowing individual letters to be changed, there are also variants in which the letters of a word can be rearranged as desired ( anagram ), or letters can be inserted or removed.

Individual evidence

  1. ^ Charles Lutwidge Dodgson: Doublets, a word-puzzle, by Lewis Carroll. Macmillan and Co, 1879. ( online )
  2. ↑ JE Surrick, LM Conant: Ladder Grams. New York, 1927.
  3. ^ Ian Stewart : Professor Stewart's Mathematical Treasures. Rowohlt, 2012. ISBN 978-3-498-06415-0 . P. 357.
  4. ↑ Jon McLoone: The Longest Word Ladder Puzzle Ever . Wofram Blog from January 11, 2012. Accessed December 27, 2013.
  5. ^ Theodore Johnson: A Random Walk Through Four Letter Words . Accessed December 27, 2013.
  6. ↑ Theodore Johnson: A Random walk through (5 to) 8 letter words . Accessed December 27, 2013.

Web links