University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Using the A* Algorithm to Find a Word Ladder

A word ladder is a sequence of words, where each differs from its predecessor by one letter. For example
WARM
WARD
CARD
CORD
COLD
is a word ladder, and is in fact the shortest possible word ladder from WARM to COLD. (There are others of the same length.)

In a computer science class at Duke University, students were required to write a program to find the shortest word ladder between two five letter English words, using Donald Knuth's database of five letter words. You can read their assignment here.

These students were instructed to use a simple breadth-first search algorithm, using a queue. However, you can do much better, by using the A* algorithm. Explain, in detail, how you would do this. One detail you may not omit: exactly what heuristic would you use?

Do not turn in any actual computer code.