# NP-Completeness of the decision problem for the generalized 15-puzzle

I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).

Now the generalization would be to extend the size of the puzzle from 15 to $p \times q$, where one field is free. I have created a small illustration (the dashed arrows show permitted moves and the lower configuration shows the solved puzzle):

Given an initial configuration of a puzzle, I ask myself the following question:

Decision question: Given a puzzle of size $p \times q$, and a number $k \in \mathbb{N}$. Is there a sequence of $k$ or less allowed moves that transform the puzzle into the solved configuration?

I already did some investigation and found the article "The $(n^2−1)$-puzzle and related relocation problems" from 1990, which shows that deciding my question for $p=q$ is NP-Complete and therefore that deciding my question is NP-Complete (as the general algorithm could also decide the question for symmetric fields).

The question that remains open is if the decision problem is also NP-Complete for fixed $q>1$. I am particularily interested in the special cases $q=2,3$. It also remains open if allowing more free spaces than one field makes the decision problem harder or easier.

All the articles I could find sadly omit the asymmetric case, thus I think there might be no known results about this. As the proof in the article is quite complicated and doesn't translate at all for fixed height, I rather hope that someone might come up with a different reduction/article that answers some of the questions.

Other related articles (to be extended):

-

## migrated from cs.stackexchange.comFeb 26 '13 at 19:31

This question came from our site for students, researchers and practitioners of computer science.

@Listing: no you cannot do it yourself, moderators can move it (perhaps they will notice these comments, and if they agree they will move it). –  Marzio De Biasi Feb 21 '13 at 13:14
I have written an unpublished implementation of Parberry's $O(n^3)$ algorithm (saml.pdf), adapted to the asymmetric case. It works :-) Also, I've been citing Erik Demaine's survey paper in my publications related to the topic. Get it at erikdemaine.org/papers/AlgGameTheory_GONC3; it's a bit newer than the 2008 paper, FWIW. –  Jonas Kölker Feb 23 '13 at 10:33

-