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

<p>I stumbled across this paper (2007):</p>

<p>"<em><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.9040&amp;rep=rep1&amp;type=pdf" rel="nofollow">The Complexity of Three-Dimensional Channel Routing</a>"</em> by     Satoshi Tayu and Shuichi Ueno</p>

<p>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.</p>

<p>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$".</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-05T21:55:04.243Z
2013-03-05T21:55:04.243Z
Listing
<p>I am interested in the natural generalization of the famous <a href="http://de.wikipedia.org/wiki/15-Puzzle" rel="noreferrer">15-puzzle</a>, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).</p>

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

<p><img src="https://i.sstatic.net/J6RpC.gif" alt="enter image description here"></p>

<p>Given an initial configuration of a puzzle, I ask myself the following question:</p>

<blockquote>
  <p><em>Decision question</em>: 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?</p>
</blockquote>

<p>I already did some investigation and found the article "<a href="http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf" rel="noreferrer">The $(n^2−1)$-puzzle and related relocation problems</a>" 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).</p>

<p>The question that remains open is if the decision problem is also NP-Complete for fixed $q&gt;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.</p>

<p>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.</p>

<p>Other related articles (to be extended):</p>

<ul>
<li><a href="http://larc.unt.edu/ian/pubs/saml.pdf" rel="noreferrer">http://larc.unt.edu/ian/pubs/saml.pdf</a></li>
<li><a href="http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf" rel="noreferrer">http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf</a></li>
<li><a href="http://erikdemaine.org/papers/AlgGameTheory_GONC3/" rel="noreferrer">http://erikdemaine.org/papers/AlgGameTheory_GONC3/</a></li>
</ul>

CC BY-SA 3.0
2013-02-21T13:08:06.200Z
I agree with Shaull
Marzio De Biasi
CC BY-SA 3.0
2013-02-21T13:14:19.647Z
@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
CC BY-SA 3.0
2013-02-21T14:25:06.523Z
Do you know http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf ?
frafl
CC BY-SA 3.0
2013-02-22T17:05:39.080Z
Just an information, what is the upper bound for the length of the solutions of a generic $n^2 -1$ instance ?
Marzio De Biasi
CC BY-SA 3.0
2013-02-22T18:18:03.367Z
@Listing: ok thank you (now I see that even in the Ratner and Warmuth there is an approximation algorithm)
Marzio De Biasi
CC BY-SA 3.0
2013-02-23T10:33:50.770Z
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 http://erikdemaine.org/papers/AlgGameTheory_GONC3/; it's a bit newer than the 2008 paper, FWIW.
Jonas Kölker
CC BY-SA 3.0
2013-02-23T10:59:04.213Z
@Listing: probably no one finds the asymmetric case particularly interesting.  Which means you get to break new ground here ;-)
Jonas Kölker
CC BY-SA 3.0
2013-02-23T11:01:05.443Z
@JonasKölker: but I think that the fixed height version (even for arbitrary large fixed $q$) is ignored because in that case (dis)proving that the moves minimization problem is NP-complete is much harder than in the unrestricted version :-)
Marzio De Biasi
CC BY-SA 3.0
2013-02-23T11:10:07.057Z
Could be.  That means you'll break a *lot* of new ground :D
Jonas Kölker
CC BY-SA 3.0
2013-02-23T11:15:55.107Z
@Listing My guess is that fixing any dimension to any constant makes the problem polynomial-time solvable but I do not have solid proof.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-23T11:37:45.300Z
@MohammadAl-Turkistany: I'll bet 1$ on NPI :-)
Marzio De Biasi
CC BY-SA 3.0
2013-02-23T11:41:20.087Z
@Vor I offer $50 cash prize for NP-completeness proof :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-23T11:43:48.853Z
@Vor If you can prove that it is in NPI then you win $1 million from Clay math.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-23T11:45:36.043Z
BTW, Is it acceptable to offer cash prizes for solutions?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-23T11:45:40.523Z
@MohammadAl-Turkistany: to be precise \$999.999 (because I have to pay the 1$ to the one who solved it for me :-)))
Marzio De Biasi
CC BY-SA 3.0
2013-02-23T11:46:41.317Z
@MohammadAl-Turkistany: perhaps a good question for Meta ...
Marzio De Biasi
CC BY-SA 3.0
2013-02-23T11:49:19.350Z
@Vor Good one :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-27T00:06:54.583Z
Related?: http://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard
Joshua Grochow
CC BY-SA 3.0
2013-02-27T16:45:15.183Z
After a quick look to the paper suggested by Joshua I bet 2$ on P :-)
Marzio De Biasi
CC BY-SA 3.0
2013-02-27T17:11:26.103Z
imho this is not precisely asked & there are 2 different problems. "Listing" refers to an "asymmetric case" ie $p\neq q$. but that is not the same as what he also asks for, "fixed q". suspect/conjecture that the $p \neq q$ case is also NP complete. conjecture that the fixed $q$ case is in P. it would be more helpful to pinpoint what construction/thm/lemma in the ratner/warmuth paper fails to work on the different geometry. the main idea seems to reduce $m \times m$ 2-2-4 SAT ($m$ vars, $m$ clauses) to "REL", a problem of relocation of elements that reside in vertices of eulerian/planar graph
vzn
CC BY-SA 3.0
2013-02-27T17:13:39.970Z
@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
CC BY-SA 3.0
2013-02-27T18:07:50.407Z
further looking, a key construction is in the appendix of ratner/warmuth paper, reducing 1/3 SAT to $m \times m$ 2-2-4 SAT. maybe the rest of the proof will work if that reduction is changed to $m \times n$ 2-2-4 SAT, $m$ clauses, $n$ vars...?
vzn
CC BY-SA 3.0
2013-02-27T18:28:06.423Z
@vzn As previously mentioned I only want to focus on fields with constant height. The transformation which gives us the initial configuration, taking an instance of "REL" seems to produce boards with polynomial height - that is why the proof would not work.
Listing
<cc.complexity-theory><np><np-complete>
NP-Completeness of the decision problem for the generalized 15-puzzle
Listing
# NP-Completeness of the decision problem for the generalized 15-puzzle

(Asked by: username_0 on 2013-02-21)

I am interested in the natural generalization of the famous [15-puzzle](http://de.wikipedia.org/wiki/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](https://i.sstatic.net/J6RpC.gif)

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](http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf)" 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):

* <http://larc.unt.edu/ian/pubs/saml.pdf>
* <http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf>
* <http://erikdemaine.org/papers/AlgGameTheory_GONC3/>

**Tags:** cc.complexity-theory, np, np-complete

> **Comments:**
> **username_1**: I agree with Shaull  
> **username_1**: @username_0: no you cannot do it yourself, moderators can move it (perhaps they will notice these comments, and if they agree they will move it).  
> **username_2**: Do you know http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf ?  
> **username_1**: Just an information, what is the upper bound for the length of the solutions of a generic $n^2 -1$ instance ?  
> **username_1**: @username_0: ok thank you (now I see that even in the Ratner and Warmuth there is an approximation algorithm)  
> **username_3**: 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 http://erikdemaine.org/papers/AlgGameTheory_GONC3/; it's a bit newer than the 2008 paper, FWIW.  
> **username_3**: @username_0: probably no one finds the asymmetric case particularly interesting.  Which means you get to break new ground here ;-)  
> **username_1**: @JonasKölker: but I think that the fixed height version (even for arbitrary large fixed $q$) is ignored because in that case (dis)proving that the moves minimization problem is NP-complete is much harder than in the unrestricted version :-)  
> **username_3**: Could be.  That means you'll break a *lot* of new ground :D  
> **username_4**: @username_0 My guess is that fixing any dimension to any constant makes the problem polynomial-time solvable but I do not have solid proof.  
> **username_1**: @MohammadAl-Turkistany: I'll bet 1$ on NPI :-)  
> **username_4**: @Vor I offer $50 cash prize for NP-completeness proof :)  
> **username_4**: @Vor If you can prove that it is in NPI then you win $1 million from Clay math.  
> **username_4**: BTW, Is it acceptable to offer cash prizes for solutions?  
> **username_1**: @MohammadAl-Turkistany: to be precise \$999.999 (because I have to pay the 1$ to the one who solved it for me :-)))  
> **username_1**: @MohammadAl-Turkistany: perhaps a good question for Meta ...  
> **username_4**: @Vor Good one :)  
> **username_5**: Related?: http://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-nnn-rubiks-cube-np-hard  
> **username_1**: After a quick look to the paper suggested by Joshua I bet 2$ on P :-)  
> **username_6**: imho this is not precisely asked & there are 2 different problems. "username_0" refers to an "asymmetric case" ie $p\neq q$. but that is not the same as what he also asks for, "fixed q". suspect/conjecture that the $p \neq q$ case is also NP complete. conjecture that the fixed $q$ case is in P. it would be more helpful to pinpoint what construction/thm/lemma in the ratner/warmuth paper fails to work on the different geometry. the main idea seems to reduce $m \times m$ 2-2-4 SAT ($m$ vars, $m$ clauses) to "REL", a problem of relocation of elements that reside in vertices of eulerian/planar graph  
> **username_0**: @username_6 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.  
> **username_6**: further looking, a key construction is in the appendix of ratner/warmuth paper, reducing 1/3 SAT to $m \times m$ 2-2-4 SAT. maybe the rest of the proof will work if that reduction is changed to $m \times n$ 2-2-4 SAT, $m$ clauses, $n$ vars...?  
> **username_0**: @username_6 As previously mentioned I only want to focus on fields with constant height. The transformation which gives us the initial configuration, taking an instance of "REL" seems to produce boards with polynomial height - that is why the proof would not work.  

---

## 1 answers

### Answer by username_0 on 2013-03-05. Score: 4

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.9040&rep=rep1&type=pdf)"* 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.


---

