In the name of Science!™, I'm trying to look for (or, in the worst case, create) a puzzle/game similar to the n-puzzle whereby a player or player(s) have to put some pieces in a particular order (e.g. in natural order in the case where the pieces are numbers) in the fewest number of moves, and there are restrictions on the possible moves of the pieces which are dependent on the positions of the other pieces on the board (e.g. in the case of the traditional n-puzzle, a piece can be moved to an adjacent position not already occupied by another piece).
Reducing likelihood of physical adjacency without increasing branching factor (much)
However, in the game I'm looking for, I need the movement capabilities of each piece to be less restricted than in the traditional n-puzzle: In the n-puzzle, there are at most four possible pieces which can move at any one time (because there is typically only one empty space and pieces can only move horizontally or vertically). Moreover, during much of the game, there are fewer than four moveable pieces, so the average branching factor of the game is actually quite low.
Physical location of pieces vs. movement
Unfortunately, e.g. allowing diagonal moves means that the game is too easy, and the moveable pieces are still all in the same physical area on the board, which I'm trying to avoid, anyway: I need to find a way to keep the moveable pieces from being "near" (i.e. adjacent to) each other on the board, so you can't just think in terms of e.g. "move the piece
- to the left of
- to the right of
the free space" — namely, you have to consciously identify the pieces without depending on their locative relationship with other pieces (the pieces also lack any obvious unique identifiers such as by being numbered: they just have abstract shapes on them, which are not necessarily unique). At the same time, the player(s) must be able to move exactly one piece at a time (no groups of pieces in one turn).
Are there any "sorting" puzzles/games which can easily be played in this way (for minimizing the amount of moves) and which still have a less "predictable" set of moveable pieces? If not, how might I go about making one? Off the top of my head, I'm thinking it might be useful to allow pieces to "jump" over each other similar to in checkers but without capturing each other — would that be a useful way to increase the number?