Shortest path from one word to another via valid words (no graph)

Question

I came across this variation of edit-distance problem:

Find the shortest path from one word to another, for example storm->power, validating each intermediate word by using a isValidWord() function. There is no other access to the dictionary of words and therefore a graph cannot be constructed.

I am trying to figure this out but it doesn't seem to be a distance related problem, per se. Use simple recursion maybe? But then how do you know that you're going the right direction?

Anyone else find this interesting? Looking forward to some help, thanks!