I agree with guest's assessment of replayability.
How about motivation to replay (before solving) instead of replayability? This is certainly something that varies from level to level. Some levels are very easy to give up on for one reason or another, while others have their way of motivating you to solve them, even if it takes a long time to discover or implement the solution correctly. I don't even know how you'd go about judging this, though. Just an idea...