1) Give the player LVL moves when he starts a new level, and when a level is complete, give him one bonus move(which carries over) for completion, and another bonus move if the solution is perfect.
2) Give the player (LVL+1) moves when he starts a new level, and any remaining moves carry over to the next level.
3) Each level has a "par" value that must be achieved in order to progress to the next round. Essentially, this would be like giving the player (2*LVL-1) moves for the round, with no carry overs.
At least in my experience, getting a perfect score in levels 1-20 is not very difficult. Getting a perfect score in levels 20-25 is challenging. 25-30 is difficult, and getting a perfect score above level 35 or so is almost impossible.
It's some kind of fast-growing curve.