I'm currently working on a turn-by-turn puzzle stealth game (as a student group project), inspired by Tiny Heist. The basic mechanic is that every time the player moves a square / does a thing, every NPC moves as well.
My objective is to make an experience similar to Portal: the player goes from room to room, each room has an entrance and an exit, with obstacles between them. The player can see where the exit is, as well as the obstacles, and must leverage the game mechanics to bypass the obstacles and reach the exit.
An example room would be:
There is a corridor, with a guard going back and forth. The exit is at the end of the corridor.
There is a closet in the middle of the corridor.
The player must exploit the guard's patrol to hide in the closet, let the guard pass him by, get out of the closet and reach the exit.
I want the player to feel perplexed when they're trying to solve the puzzle; ideally, I want them to feel there is a solution just within their grasp, but they can't find it; and I want them to feel smart once they do solve the puzzle.
The problem is, I don't know how to design puzzles to give that experience. I have a few ideas, some of which feel like they'd make fun "early game" levels, but after a while all the levels I'm sketching feel same-y and boring, or too complicated with too many moving parts (I had the same problem back when I tried to design Portal 2 levels).
I want to create dependencies, levels where the mechanics overlap with one another to make the player think "I need to do X, but I can't do X before I've got Y, but how do I do Y without having done X?". I could add additional mechanics like dogs, or security cameras, but I don't know how to exploit them.
When I try to design a level, the kind of ideas I come up with follow a pattern of "you need to turn off the cameras to progress, but you need to give a bone to the dog to reach the camera, but you need to distract the guard to acquire the dog". These ideas are convoluted, but shallow; they don't feel like they'd make for intellectually stimulating (or even difficult) levels.
What methodology or design pattern can I apply to create richer problem-solving opportunities for the player in this stealth game context, or in any kind of puzzle game?