The key to a good puzzle is the "aha!" moment: when the player solves it, they should feel a buzz of satisfaction because they were clever enough to outwit the creator. Maybe there was a component whose purpose wasn't obvious, and when you thought hard enough about the question "why was this even included?" you spotted a cunning way to use it. Maybe there was a really plausible first move they were automatically making, but it turned out to be a red herring. Maybe the correct first move was something they were automatically rejecting because it looked so bad.
The flip side of the "aha!" moment is frustration; you can't get that feeling of satisfaction without first being frustrated, feeling that the solution must be inches away and yet you somehow can't see it. This means you have to tread a dangerous line: too much frustration and you risk the player being turned off and giving up on the puzzle.
There are a few ways around this. Firstly, start with simpler puzzles and then work up to more complex ones: that allows the player to get used to the mechanics, and gives them the feeling that they enjoy solving this type of puzzle, and that gives them more determination to persist when they get stuck. Secondly, teach the player the rules and then stick to them -- the player should never feel that they failed at a puzzle because they didn't know the rules. Thirdly, give the player a sense of progression: sometimes even if you can't see the complete solution to a puzzle, you can feel that you are getting closer because certain components are falling into place, and you get some kind of feedback letting you know you are on the right track.