```> My current solution works correctly with various inputs.
> It might have bugs, but most importantly, it takes forever.

My solution takes under a minute on my machine; the majority is the
building of the word hashes.  Some of the basic techniques are:
* Store the words in the sorted form, rather than sorting them each
time
* Start with the longest words, and stop trying when our chain is
longer than the length of the words we are trying
* Store the words organized by length, so we can iterate starting with
the longest words
* Store the maximum chains for a given set of letters, so we don't
need to recompute it

The code is reasonably short as well.  I suspect it could be optimized
further:
#!/usr/local/bin/ruby

\$File = "WORD.LST"
\$Lengths = Hash.new
MaxWordLength = 30
(MaxWordLength+1).times {|i| \$Lengths[i] = Hash.new}
\$MaxChains = Hash.new

num = 0
puts "#{lines.length} total words"
\$stdout.sync = true
lines.each {|w|
num += 1
print "#{num}\r" if (num % 1000 == 0)
w.chomp!
\$Lengths[w.length][w.split(//).sort.join] = w
}

def getMaxChain(letters)
return \$MaxChains[letters] if \$MaxChains[letters]
length = letters.length
w = \$Lengths[length][letters]
maxChain = [w]
letters.length.times {|i|
chain = [w]
lessOne = letters.dup
lessOne[i] = ''
smaller = \$Lengths[length-1][lessOne]
if smaller
chain.concat(getMaxChain(lessOne))
maxChain = chain.dup if chain.length > maxChain.length
end
}
\$MaxChains[letters] = maxChain.dup
maxChain
end

maxChain = []
MaxWordLength.downto(1) {|length|
puts "Trying words of length #{length}"
words = \$Lengths[length]
next unless words
words.each {|letters, word|
chain = getMaxChain(letters)
maxChain = chain if chain.length > maxChain.length
}
break if maxChain.length > length
}
p maxChain.reverse

--
Steven
If God had wanted us to be concerned for the plight of the toads, he
would
have made them cute and furry.
```