# Word ladders - source code

This is a resource of the wordgame-programmers@egroups.com mailing list.

Click to subscribe to wordgame-programmers

Here is a wide selection of algorithms for solving the Lewis Carrol "Doublets" game. Generally these are a breadth-first search, at least if done properly. Actually a variant of depth-first search called "Iterative depth-first search" aka "iterated deepening" is almost like a breadth-first search and is sometimes appropriate in problems like this; This is an explanation of Iterative Deepening from a paper on Chess search trees:
Iterative deepening means repeatedly calling a fixed depth search routine with increasing depth until a time limit is exceeded or maximum search depth has been reached. The advantage of doing this is that you do not have to choose a search depth in advance; you can always use the result of the last completed search. Also because many position evaluations and best moves are stored in the transposition table, the deeper search trees can have a much better move ordering than when starting immediately searching at a deep level. Also the values returned from each search can be used to adjust the aspiration search window of the next search, if this technique is used.

• ladder & letterbank code in C/
A dynamic programming solution (in plain C) to find lowest-cost ladder, allowing either letterswaps (scoring 1 pt) or letterbanks (scoring 3 pts).

What is a letterbank? - take the unique letters in a word, and find another word which is made from only those letters, with each letter appearing at least once. Letters may be used multiple times. For example, ACCOUNT can be letterbanked to COCOANUT.

The code pre-builds a table of all links from a word (whether transformed by letterswapping or letterbanking) and replaces word strings with indexes representing the words. The shortest-path solution works in graph space, and does not handle words at the letter level at all.

Steve Thomas's C code to find shortest and toughest! word ladders. (Steve is also a writer of competitive Scrabble programs)
C++ source to do a breadth-first search using C++ libraries
Complete source for a word-ladder game for PCs in non-portable Pascal. From PC Magazine.
Portable ISO Pascal source for fixed length ladders (4 and 5 letters), with machine translation into C. (A good C translation would restructure the code and make the game length independent) Includes p2c translator for good measure!
Fairly readable (in the pascal version) and good for learning the breadth-first-search algorithm. Fast.
• sgb/
This is a general purpose package for graph algorithms from programming Guru Don Knuth. Like all his work, it is brilliant, but he doesn't have a clue about making it accessible (unless of course you install tangle, weave, cweb, Tex, etc etc first). If only he had written a webtohtml converter, life would have been so easy. Anyway, this is basically the same algorithm as the example above, but I don't recommend it for beginners. However, advanced programmers who have complex graph algorithm problems to handle, related to words, may find this an invaluable tool.
• rfrank/
Similar to Knuth's algorithm, but a little more readable, is Roger Frank's code to implement word ladders in C++
• craigcopi/
Perl script to solve word ladders.
Uses a pre-built trie.
• potm/old-problems/doublets.txt
An old entry for the "Programmer of the Month" competition was just this problem. Unfortunately I can't find the old solutions.

There are some tangentially related games which might be worth mentioning here:
Note that a ladders game coupled with extending or shrinking words is remarkably close to some other games like the British variant of Lexicon.