Word ladders: Carroll’s dictionary and the shortest route
Word ladders connect equal-length words through single-letter substitutions. Lewis Carroll developed his version around Christmas 1877, initially calling it Word-Links. After trying it with family and friends, he offered the pastime to Vanity Fair, which introduced Doublets in March 1879. His rules fixed the positions of the letters: a substitution could replace a letter, but could not move the remaining letters around. The game combined a vocabulary restriction with a restriction on movement. [1, 2]
The sequence head -> heal -> teal -> tell -> tall -> tail joins the two endpoints in five substitutions. It contains four intermediate words. Carroll called those intermediate words links, the two endpoints a doublet, and the entire sequence a chain. The distinction between links and substitutions affects the count: four interior words sit between five successive pairs. His example used ordinary English vocabulary while making the change from a head to a tail visible through intermediate spellings. [1, 2]
Carroll’s 1879 collection also allowed specified intermediate words. These set links had to occur in the prescribed order, and such a chain could not contain the same word twice. A doublet with two set links was divided into three portions. Scoring treated those portions separately: a four-letter doublet with two set links carried 24 available marks, compared with eight for a four-letter doublet without them. Shorter admissible chains earned the full available score. [1]
Vocabulary soon required its own machinery. Carroll compiled a glossary covering words of three, four, five and six letters. Regular comparative and superlative forms counted as inflections of their adjectives or adverbs. A noun derived from a verb did not automatically qualify: its inclusion required a separate glossary entry. A common spelling could also serve more than one grammatical role, with entries arranged to supply the needed inflections. [1]
The glossary remained fixed during a competition. Proposed additions or removals had to be accompanied by two other words showing the disputed word between usable neighbors. Alterations were announced before a new competition began. These arrangements made admissibility a shared rule rather than a decision improvised for each submission. Carroll aimed for a vocabulary that educated participants could carry in memory, with the glossary available to settle doubtful cases. [1]
The first published groups mixed three-, four- and five-letter transformations. On March 29, 1879, they included pig and sty, four and five, and wheat and bread. Later groups included pen and ink, chin and nose, and tears and smile. The endpoint pairs supplied verbal images as well as spelling restrictions. A pair could suggest a movement, a transformation or a relationship while the actual permitted steps remained substitutions of single letters. [1]
Computer searches turn word ladders into shortest-path problems. Stanford’s CS106X teaching materials describe a breadth-first search that examines all routes one substitution from the beginning, then all routes two substitutions away, and continues outward. A route found at the first successful depth has minimum length. Several routes may tie for that minimum; the movement rule does not require a unique route between every pair of endpoints. [3]
The search uses an English dictionary to decide whether a proposed intermediate spelling is admissible. Replacing one character can generate candidates, which are retained only when the dictionary contains them. Stanford’s procedure keeps partial routes in a queue and records words already encountered, avoiding repeated searches through the same spelling. The vocabulary and search order perform different jobs: one defines the permitted words, while the other organizes exploration of their connections. [3]
Donald Knuth’s Stanford GraphBase supplies another connection between words and combinatorial computing. Knuth's page lists it as an ACM Press book dated 1994, and describes it as combining programs with standard sets of data for benchmark tests of competing methods. Its publicly available word file contains 5,757 five-letter English words. The collection also includes data about neighboring American states, railway travel and encounters among literary characters. Words belong to a broader supply of concrete material from which combinatorial examples can be built. [4]
Word ladders entered the magazine through three introductory weekly groups before the first sustained competition. The preliminary dates were March 29, April 5 and April 12, 1879; the competition ran from April 19 through July 26. Weekly totals recorded participants’ accumulated marks. Extra links beyond the shortest admissible chain cost one mark apiece, down to zero. The glossary was intended to settle word validity consistently across those successive rounds rather than changing the permitted vocabulary halfway through a competition. [1]
The GraphBase programs and data are publicly available, and its examples combine explanatory writing with executable programs. Knuth describes the collection as a workbench for combinatorial computing, including demonstrations and games. His downloadable vocabulary fixes one particular collection of five-letter words, while Carroll’s glossary admitted several lengths and specified inflection rules. Word ladders therefore have both a linguistic boundary and a computational structure: accepted spellings determine the available connections, and a search determines routes through them. [1, 4]
[1] Lewis Carroll, Doublets: A Word-Puzzle (1879), primary text. https://schnark.github.io/lewis-carroll/html/texts/doublets-a-word-puzzle.html
[2] Lewis Carroll Resources, Doublets: historical introduction and original rules. https://lewiscarrollresources.net/doublets/index.html
[3] Stanford University CS106X, Assignment 2: Word Ladder and breadth-first search. https://web.stanford.edu/class/archive/cs/cs106x/cs106x.1192/assignments/adts.html
[4] Donald Knuth, The Stanford GraphBase: programs and word data. https://www-cs-faculty.stanford.edu/~knuth/sgb.html
- Lewis Carroll, Doublets: A Word-Puzzle (1879), primary text — schnark.github.io