One way to do it with puzzle games is to start from the end and create the level in reverse.
This has the added bonus that all your puzzles are guaranteed solvable.
Finding the absolute minimum number of steps might be good for a university paper but you don't need to find it for a good game. Players love finding better ways to solve the puzzle. The ego boost adds to the fun.
Sounds like I'm dodging the question but since this is game development rather than computational science (http://scicomp.stackexchange.com/https://scicomp.stackexchange.com/) the most important thing for games is "Is it going to be fun?" over "Is this the perfect solution?".
Cheers,