Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question

migrated from cs.stackexchange.com Feb 26 '13 at 19:31

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

2  
@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
2  
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
4  
@Vor I offer $50 cash prize for NP-completeness proof :) –  Mohammad Al-Turkistany Feb 23 '13 at 11:41
2  
2  
@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. –  Listing Feb 27 '13 at 17:13
show 22 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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