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):

enter image description here

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):

  • 2
    $\begingroup$ @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). $\endgroup$ Feb 21, 2013 at 13:14
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 23, 2013 at 10:33
  • 4
    $\begingroup$ @Vor I offer $50 cash prize for NP-completeness proof :) $\endgroup$ Feb 23, 2013 at 11:41
  • 2
    $\begingroup$ Related?: cstheory.stackexchange.com/questions/783/… $\endgroup$ Feb 27, 2013 at 0:06
  • 2
    $\begingroup$ @vzn Sorry if I was not specific enough here - I only want to ask for fixed q, which is a special form of the asymmetric case. $\endgroup$
    – Listing
    Feb 27, 2013 at 17:13

1 Answer 1


I think that I found a partial (although quite disappointing) answer to my problem:

I stumbled across this paper (2007):

"The Complexity of Three-Dimensional Channel Routing" by Satoshi Tayu and Shuichi Ueno

They show (Theorem 4) that the "3d-channel routing problem" with "2-nets" and dimension $p,q$ can be solved if and only if the corresponding (check article for more details) $p \times q-1$ puzzle can be solved.

Below Theorem 1 they propose some problem they call "2.5-D CHANNEL ROUTING", which is basically "3d-channel routing" with fixed depth $k$. They also say "the complexity of the following problem [2.5-D Channel Routing] is open for any fxed integer $k \geq 2$".

If we knew that the decision version of the $p \times q-1$ puzzle is NP-Complete for some fixed $k \geq 2$ we would also know that 2.5-D Channel Routing is difficult for that $k$, therefore it seems the question can be reduced to some open problem.

It could of course be that the answer to my question would be that $p \times q-1$ puzzle is in P for all fixed $k$, which would still leave their question open (as the general routing doesn't only handle $2$-Nets). Therefore this is no complete answer, it is also rather disappointing that they include no references when claiming that the problem is still open.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.