I am writing a simple word game, where the computer randomly selects two four letter words, and the object is to go from the first word to the second word by changing only one letter at a time, like this: Go from "help" to "this" help hell hail tail tain (it''s a word) thin this Every step has to be a real word. I have a text file containing thousands of four letter words. My question is this: how can I write an algorithm that can automatically solve any such puzzle?

I missed a step: hell should go to hall then to hail

quote:Original post by TSwitch
Calling it A* is like calling a peanut butter sandwich ... something very complicated. Also, isn''t it more like Dijkstra''s? You can''t really say which node is going to get there first, heuristic won''t save you...

Just think of a tree, where each word node has children that are only 1 letter off for the parent (neighboring nodes in a search). No child node may have the same word as a parent (No doubling back in a search). Eventually, Mr. Tree will find the target word in one of the child nodes. That == "yey" condition.

Building that tree could be, well, ugly--consider: hall->half->calf->call->hall is suddenly circular, four layers deep. Also, since hall can be a child of call and half, there''s a parenting issue. What you''d need to do, I guess, is to do a breadth-first search to build the tree dynamically (that is, use the given starting word as your root node; you can''t build a general-purpose tree beforehand); if a word is already in the tree, then it just isn''t added. This requirement (searching the tree to make sure you''re not putting in an already extant word) slows things down considerably. Doing some pre-processing to build up the possible relationship table would help; when a word is added to the tree, it should be removed from the table--this eliminates the need for searching the tree. In that case, it basically boils down to a breadth-first search (Dijkstra''s, as suggested) powered by a prebuilt table.

I agree that A* is very wrong for this problem--A* works for acyclic, weighted graphs (with a decent heuristic); this, however, is a cyclic, non-weighted graph with no good heuristic possible.

Hope that helps.

-Odd the Hermit