Here's my solution,
It's another bidirectional breadth first search
I coded it up before I saw all the others, but I think it ended up
being pretty similar.
-Adam
---
# Ruby Quiz Word Chain Solution
# Adam Shelly
# Late August, 2005

# Usage wordchain [-d dictionary] [-l] word word ...
#   finds chains between every pair of words on the command line.
#   uses dictionary file specified by -d, or /usr/share/dict/words by default.
#   if -l is specified finds the longest chain from each word.

class String
    def shift
        self.slice(1,length-1)
    end
    def parent= p
        @parent = p 
    end
    def parent
        @parent
    end
end


class WCSolver
    #Loads only the words with a given length.  
    #didn't add much speed, but saves memory.
    def initialize(wordlist, length)
        @t = Hash.new
        @len = length 
        add_words(wordlist)
    end
    
    def add_words(wordlist)
        w2=nil
        wordlist.each {|w| @t[w2]=true if (w2=w.strip).length == @len }
    end

    def neighbors word
        list = []
        word.size.times do |i|
            w = word.dup
            w.parent = word
            ?a.upto(?z) {
                |c|w[i]=c 
            	list << w.dup if (@t[w] )
            }
        end
        list.uniq
    end

    #bidirectional breadth first search
    def solve first, last
        puts "Connecting #{first} -> #{last}"
        return nil if @len && (first.length != @len || last.length != @len)  
        seenhead, seentail, match = [],[],[]
        head,tail = [first],[last]
        while match == []
            r = head.collect{|w| neighbors(w)}.flatten - seenhead
	    return nil if r == []
            seenhead += head = r
            match = head & tail
            break unless (match == [])
	    r= tail.collect{|w| neighbors(w)}.flatten - seentail
	    return nil if r == []
	    seentail += tail = r
	    match = head & tail
        end
        r = [ head.find {|w| w==match[0]}]
        while r[-1].parent do r << r[-1].parent end
        r.reverse!
        r[-1]=tail.find {|w| w==match[0]}
        while r[-1].parent do r << r[-1].parent end
        r
    end

    def longest from
        puts "Longest Chain from #{from}"
        seen,head  = [],[from]
        while true
            r= head.collect{|w| neighbors(w)}.flatten - seen
            break if r == []
            seen += head = r
        end
        l = [head[0]]
        while l[-1].parent do
            l << l[-1].parent
        end
        l.reverse!
    end
end
 
if $0 == __FILE__
    puts "Wordchain Finder\n"

    file = ARGV.slice!(ARGV.index('-d'),2)[1]   if ARGV.include?'-d'
    file ||= "/usr/share/dict/words" 

    showlong = ARGV.slice!(ARGV.index('-l'),1) if ARGV.include?'-l'
    length = ARGV[0].length if ARGV[0]

        wordlist = File.new(file, "r")
    if (wordlist)
        s = WCSolver.new(wordlist,length)
        while (w = ARGV.shift)
            unless (showlong)
                puts s.solve(w, ARGV[0]) if ARGV[0]
            else
                puts s.longest(w) 
            end
        end
    end
end