Thanks for the suggestion. I think of adding a time spend to complete the level :)
Can you also add number of left over moves as a factor too?
I might try to generate levels where you will always have to use all moves...
But why? It's nice to find out that you didn't need to use all the moves to solve the puzzle. Right?
Edit: Maybe you could also add a time limit?