I'm currently creating a game, that mixes traditional platformer elements (jumping on enemies, collecting coins, etc) with puzzle based gameplay, something similar to the Zelda series, for those who played it.
In each stage, there are several ways the player can screw up, and be unable to continue.
Some examples:
- Some stages contain bombs, that can be used to blow some walls up. They are availiable in very specific places and quantities, so the player needs to think where to use them.
But in case you use it on the wrong place, sometimes it is not possible to complete the stage unless the player restarts again from the beginning.

- Some stages contain blocks that can be pushed, a bit like the classic Sokoban. Pushing a block into a corner for example, sometimes makes it impossible to move it again (players cannot pull, the character itself does not have arms). In this case the level needs to be restarted too, otherwise there's no way to finish it.

I've added a 'Restart' option to the pause menu. But that means that the players themselves need to decide when they think it is not possible to continue anymore and restart (and sometimes they may be wrong).
Another possibility would to try to detect the conditions where the restart is needed, and tell the player a message telling that.
This would be very difficult to implement, and maybe won't even detect all possibilities (the game is a bit like those sandbox physics games). Also by telling the players that they need to restart, this would help them to find the right solution faster, I think, and that is not good.

Should I just leave the option to restart manually and players would be ok with that?

I see, well, from what we've been testing, most players spend around 10 to 20 minutes in the stages of my game. I suppose that restarting frequently on those levels would not be a problem.

Have you thought about checkpoints? For the bomb segments you could put them in places where you don't need old bombs to progress, and for the block puzzles they can be at any point close before it.

Have you thought about checkpoints? For the bomb segments you could put them in places where you don't need old bombs to progress, and for the block puzzles they can be at any point close before it.

Well, that would be difficult, since the player can generally wander all over the stage, with the exception of some parts that may be out of reach until a puzzle is completed.

What about a rewind feature similar to Braid? This way the player can rewind to the part where they made the mistake. Of course, they would have to be able to know where the mistake was and that they made it.

Of course, they would have to be able to know where the mistake was and that they made it.

Oh, this is actually the main reason behind my post. Should I try to tell the players that a mistake was made or should I let them guess themselves?
I would prefer the later, since it allows the players to experiment new things without being constantly told by the game that they are doing it wrong, but I'm not sure, it seems like today's gamers feel the need to be guided somehow.

As long as the mistake is quite evident (I need to blow up something and I have already used all my bombs or the sokoban example), I think it's ok to leave the player free to experiment. But I don't like to replay a part of a game repeatedly and I prefer to have some ways to "correct" the mistakes I have done. I think you should leave some room for errors to the player so that they can experiment without having to replay after each error.