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.


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.