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_thomas/
Steve Thomas's C code to find shortest and toughest! word
ladders. (Steve is also a writer of competitive Scrabble programs)
- pcladder/
Complete source for a word-ladder game for PCs in
non-portable Pascal. From PC Magazine.
- ladder/
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.
- Warwick Allison's word-ladder program
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.
Return to the Archive overview.