IMO it's fine for the player to get stuck, as long as the game communicates it clearly. I don't mind resetting the puzzle all day as the game tells me I have no moves left the moment it happens. I think the only way I get frustrated with these styles of games is when I'm stuck but I'm not sure if there are still moves left I'm not noticing. Worse yet is when the game is adding a new mechanic to a level and I get stuck and I'm not sure if its because I'm not using the new mechanic properly or if I'm legitimately out of moves.
Some games like Puzzle Quest don't even wait for the player to reset if there are no moves left - they just explode the board and reset everything right away.