I'd also like to point out that you could have one "normal" difficulty level, but then add extra difficulty for those who want to achieve "expert status". Like... to be able to solve a level on could simply walk from door A to door B - that would be easy. But, if the player decides to collect coins, find secret treasure, kill the dragon and save the princess then he would achieve "expert status".
This would make it easy to pass the levels (especially nice when you are stuck with some one stupid level and couldn't care less about slaying the dragon

)... but it would also give challenge for those who want it.