Wordladder

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

Problem Description

The challenge of Word Ladders is to transform one word into another by changing one letter to make a new valid word at each step.    For example, we can change CAT to DOG in 3 steps with the sequence CAT, COT, COG, DOG.      

Here's a program that solves word ladder puzzles.  

Background & Techniques

WordLadder is another graph searching exercise, this time the vertices are words that differ from adjoining vertices by a single letter.   

It uses the TDict class introduced in WordStuff1  to access a dictionary of valid words.  For faster access, the words of a specific length are read from the dictionary and saved as a text file the first time that length is encountered.  The text files are then loaded into WordList, a TStringlist object, as required. 

Depth-First Search

The first implementation was a depth first search that uses recursion like this.  The recursive routine, MakeDFLadder, takes two parameters - the starting word and the position that was changed to produce that word.  The initial call is MakeDFLadder (fromword, 0). When we enter, we'll add the word to the SolutionListBox list, the list that is displayed to the user.  We'll loop through WordList looking for valid words that differ from our starting word in only one letter position with that position not  the same one we just changed.   (This second condition was added to eliminate sequences like DOG, BOG, FOG, JOG, JAG ...  which could have been shortened to DOG, JOG, JAG..., etc.)   All the words that match and are not already in SolutionListBox list are placed in a temporary sorted stringlist of all candidates.  The words are prefixed by the string representation of the number of letter positions that do not match the target word.  This has the effect of putting words that that are closest to the solution at the beginning of the list and should lead us to a solution in a shorter time.    For example,  in our original CAT, COT, COG, DOG example,  02COT (differs from DOG in 2 positions) will appear before 03CAR and 03FAT  (differing in all 3 letter positions) in our temporary list.  While doing this, we might as well check to see if the difference from the target is one.  If so, we have found a solution and might as well stop here.

Otherwise, when the temp list is built, we'll loop through, stripping the numeric prefixes and making  recursive calls to MakeDFLadder for each entry until a solution has been found (Result is true) or we've processed entire list.  If we run out of words and no solution has been found, remove the word from SolutionListBox and exit.  This will send back to the preceding level in the recursion.

Breadth-First Search.

While depth-first searches generally not  find the shortest path to a solution, breadth-first will.  We are checking all of the possible solutions of length 2, then all of length 3, etc.  So if we find a solution at all, we know that there is none shorter. 

This search is not recursive.  At each level we can make a new list of all the words that might lead us to the solution at the next level, we assign a numeric prefix and sort them by closeness to the target as we did with depth-first.  Then, if we don't find a solution at this level, assign that next-level list to the current level list and repeat.   The new problem is that  when we do find a solution, we have no idea of how we got there!.   The solution is to carry a "predecessors" list along with each word which contains the information about how we got to it.  Then when we get to a solution, that list is the solution to be displayed.  I'll leave it for the reader to study the code to see implementation details if interested.  

There is a common Solveit routine that serves as a wrapper for the code common code to both depth and breadth-first searches.  Also the usual provisions to allow the user to stop execution for long searches.  A MaxLevel user input field limits the length for both search types.  

I've provided a listbox with a roughly graded list of other word pairs, including one or two that may have no solutions (or maybe I just haven't allowed them to search deeply enough).

Enjoy!

Running/Exploring the Program 

bulletDownload Dictionary files (only required if you haven't downloaded previously with WordStuff series)  
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

I'm sure that the search speed could be improved - one possibility is to build a tree (maybe with the TTreeView component or an adjacency list structure) in advance for words of a specific length.  This would be streamed to a file in place of the current text word lists.  Searching then could directly generate all possible next words without processing the entire word list. 
Allowing user play would is a potential enhancement.  The program would simply check that entries are valid and flash a reward when the solution was reached.
Word Ladder is a natural to include as a called module from the WordStuff program previously posted.

     

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2013, Gary Darby    All rights reserved.