Are there any resources for motion-planning puzzle design?

Question

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.

Answer 1

It seems to me that most of these types of puzzles can be related to solving an over-constrained system of equations that happens to have a solution. I'm not sure if that makes sense, but if you can somehow relate your rules to a system of equations, then build "solutions" from what you know the answer to be, it might lead to interesting problems. It also means that the puzzles are entirely mathematical and not "motion-like" at all. Just a bunch of static equations :-)

Another way of looking at it is considering that the simpler types of these puzzles have direct solutions --- that is, move a piece, then another, then another & then it's solved!, but the more complicated ones can force you down a path that doesn't seem obvious at first. Start from the final solution and applying your rules in reverse to complicate the initial conditions will also help. Looking at each rule application as a branch on a tree or graph, the interesting puzzles are very dense with only one or two paths that lead to solutions instead of many paths that lead to solutions.

Answer 2

For the most part it's easy to generate these puzzles by starting at the solution and iteratively choosing objects to move or mutate until you reach a suitable start point. The player then has to perform the same steps (or equivalent) in reverse order, and the more steps you used, the harder it is likely to be for them to solve it.

I'm not sure it would be practical to have any way of auto-generating puzzles that rely on different classes of sub-problem however; that would probably require a human mind to identify these areas and exploit them.