Some background: I'm poking at a set of puzzles along the lines of Rush Hour/Sokoban/etc; for want of a better description, call them 'motion planning' puzzles - the player has to figure out the correct sequence of moves to achieve a particular configuration. (One characteristic of the sort of puzzle I'm thinking of is that they're generically PSPACE-complete; they're not necessarily in NP because the optimal sequence of moves isn't necessarily polynomial in the input size, so we can't guarantee that a solution can be verified in polynomial time).
While I have a few straightforward 'building blocks' that I can use for puzzle crafting and I have a few basic examples put together, I'm trying to figure out how to avoid too much sameness over a large swath of these kinds of puzzles, and I'm also trying to figure out how to make puzzles that have more of a feel of logical solution than trial-and-error. Does anyone know of good resources out there for designing instances of this sort of puzzle once the core puzzle rules are in place? Most of what I've found on puzzle design only covers creating the puzzle rules, not building interesting puzzles out of a set of rules.