Word ladder
Word line is the name of a letter puzzle. The aim is to combine two given words of equal length by a chain of words by just exchanging one letter in each step. So one can HALM in KORN change through the chain HALM STOP HART HORT HORN KORN. To make the puzzle appealing, often two words are chosen as in this example, which are also content in a compound, so are about opposites or, as here, the one developed from the other.
History
The puzzle is busy writing at least since 1879. This year, the magazine Vanity Fair published under the name Doublets a series of puzzles of this type, which had Lewis Carroll designed and provided with a set of rules for awarding points. In the same year the puzzles published in book form. Carroll writes that he had heard from an American game that is based on a similar principle, the puzzle have been developed independently of it, in order to entertain at Christmas 1877 two girls.
1927 published Surrick JE and LM Conant a book Ladder Grams, which contains such mystery.
Theoretical investigation
The puzzle can be studied theoretically by considering the graph in which the vertices represent the words and an edge is drawn if the corresponding words differ in exactly one letter. For two words then establish a link if and only find out if they are in the same connected component, the shortest link can be with the Dijkstra algorithm to determine.
One of the first analyzes of the resulting graph comes from Donald E. Knuth, the case in English coined the term aloof ( off ) for the words which have no link, aloof is an example of such a word itself.
The results of Erdős and Rényi on random graphs make it seem plausible that there is a 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 conclusion also various studies of the graphs that are formed by English words of different lengths.
Variants
Instead of allowing only the altering of single letters, there are also variants in which one can change the letters of a word arbitrarily, or even add letters or can remove.