Some n-puzzle ideas:

1. Create an n-dimensional n-puzzle.  This is different from a rubiks cube because it is a sliding puzzle not a sequential move puzzle.  It is sort of like the last puzzle here called the Inside out puzzle by Vadász Kocka, it is of course only 3D not nD.
2. Figure out how to reduce nD n-puzzle to 1D n-puzzle (meaning make a new set of rules for how the pieces move and in a way that eliminates symmetric moves)
3. The number of ways to solve an n-puzzle is in #P (find proof)
4. Can any unsolvable n-puzzle be solved with some number of flips and rotations to the board itself?
5. What would it mean to have a fractional dimensional-puzzle like a 1/2d n-puzzle? How could you move?
6. What if the puzzle is represented as a graph.  Then you can represent it as an adjacency matrix and do math (haha).

I found the paper that proves that n-puzzle is NP-hard here.  Also, I found some papers that cite that paper that I thought sounded interesting:

1. Optimal Pebble Motion on a Tree
2. Learning Admissible Heuristics while Solving Problems
3. On Sliding Block Puzzles
4. Wooden Geometric Puzzles: Design and Hardness Proofs
5. Restricting Moves When Solving the NxP-Puzzle

In writing this I found an amazing source of puzzles here.  It is an index of over 34,000 puzzles!

So, I think that the most interesting of the ideas is 4.  The dimensional aspect I think is a direct mapping of the space and therefore not too interesting.  The fact that it is in #P is sort of interesting but kind of obvious and not really useful.  The interesting thing with that one would be if it was somehow either harder or easier than #P.

So, number 4 is interesting because it is a new way of looking at the board.  However, I believe the answer is yes.  According to the 5th link the number of possible board states is (N*P)! and half of them are not solvable.