I appreciate your idea as well digitprop. I was considering doing something similar, but wasnt sure if it was extremely inefficient.
It does sound inefficient at first, but it really depends on how far your unit is going to move. If the average move is, like in your example, only 5 spaces, then a simple KISS-style recursive algorithm should do the job. Depth first search (which I think this algorithm is) has, indeed, an exponential order of growth in terms of speed (not too much space is used though). Nevertheless, just like in the traditional Queens problem, the number of choices (again, this depends on how far a unit can move and how expensive the tiles are) will be relatively low at each step.
Now it sounds like I'm repeating what digitprop said. I guess I'm trying to say that Depth first search is not too bad if the number of choices dramatically decreases at some point.
EDIT: add some stuff:
Also, I don't think speed should matter too much, although it grows exponentially. Computers these days are relatively fast
I think the only major problem you could encouter using this (or any) recursive approach is getting too big of a method call stack.