На самом деле 626 слов это наверно даже лучше=)
Я решал эту задачу на PHP на собеседовании, с использованием этого же словаря.
Моя цепочка была муха + 455 слов + слон. Ну или 456 не считая мухи.
Решение назвали единственно верным, после чего я решил, что больше 456 быть не может.
а у меня не ищется самая короткая цепочка... вот, например, франгмент:
"река -> дека -> чека -> чека -> щека"
почему-то чека два раза, да и вообще всю цепочку можно заменить на "река -> щека"
Update: проверил исходный словарь. 2360 4х-буквенных слов, из которых только 2332 неповторяющихся у меня алгоритм перебирает все варианты по порядку, и останавливается на первом подходящем...
можно попробовать удалить из результата такие вот лишние преобразования, есть вероятность, что тогда результаты сойдутся. Надо?