In this type of situation, the players must applying thought to find the proper solution. This can be tricky. You don't want the players to get frustrated by making it too hard, yet you don't want to make it too easy either. The sweet spot is when they not only solved the situation, but feel that it was a worthy accomplishment.

The biggest consideration is failure. If they fail, will it ruin the plot or the player's fun?

One solution is to make the puzzle one that can be retried, so failures have no detrimental effect. The only problem is that players may never solve the puzzle. The game master must therefore be prepared to supply clues that help the players but don't make them feel they were just given the answer.

The standard form of this situation is that something must occur and that thing can only occur if you figure out how it could be done. The opposite senario is also a possibility, that the players must foil someone else's repeated attempts. For instance, instead of figuring out a way to kill the evil king, the players could defend the good king against repeated attempts against his life.