NP-Vollständigkeit des Entscheidungsproblems für das verallgemeinerte 15-Puzzle

Ich interessiere mich für die natürliche Verallgemeinerung des berühmten 15-Puzzles , bei dem Sie Blöcke schieben müssen, bis Sie alle angegebenen Zahlen sortiert haben (normalerweise gibt es eine Lücke von 1 Block).

Die Verallgemeinerung wäre nun, die Größe des Puzzles von 15 auf , wobei ein Feld frei ist. Ich habe eine kleine Illustration erstellt (die gestrichelten Pfeile zeigen erlaubte Züge und die untere Konfiguration zeigt das gelöste Rätsel):$p \times q$

Bei einer anfänglichen Konfiguration eines Puzzles stelle ich mir folgende Frage:

Entscheidung Frage : ein Puzzle von Größe Gegeben und eine Anzahl k ∈ N . Gibt es eine Folge von k oder weniger erlaubten Zügen, die das Puzzle in die gelöste Konfiguration verwandeln?$p \times q$$k \in \mathbb{N}$$k$

Ich habe bereits einige Nachforschungen angestellt und den Artikel " Das -Puzzlespiel und damit verbundene Umsiedlungsprobleme$(n^2−1)$ " aus dem Jahr 1990 gefunden, aus dem hervorgeht, dass die Entscheidung für NP-vollständig ist und daher die Entscheidung für meine Frage NP-vollständig ist. Vollständig (da der allgemeine Algorithmus auch die Frage nach symmetrischen Feldern entscheiden könnte).$p=q$

Die Frage, die offen bleibt, ist, ob das Entscheidungsproblem auch NP-Complete für festes . Ich interessiere mich besonders für die Sonderfälle q = 2 , 3 . Es bleibt auch offen, wenn das Zulassen von mehr als einem Feld das Entscheidungsproblem schwieriger oder einfacher macht.$q>1$$q=2,3$

Alle Artikel, die ich finden konnte, lassen den asymmetrischen Fall leider aus, so dass ich denke, dass es keine bekannten Ergebnisse darüber geben könnte. Da der Beweis in dem Artikel ziemlich kompliziert ist und sich für eine feste Höhe überhaupt nicht übersetzen lässt, hoffe ich eher, dass jemand eine andere Reduktion / einen anderen Artikel findet, der einige der Fragen beantwortet.

Weitere verwandte Artikel (zu erweitern):

• 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/

Ich denke, dass ich eine teilweise (wenn auch ziemlich enttäuschende) Antwort auf mein Problem gefunden habe:

Ich bin auf dieses Papier gestoßen (2007):

" Die Komplexität der dreidimensionalen Kanalführung " von Satoshi Tayu und Shuichi Ueno

$p,q$$p \times q-1$

$k$$k \geq 2$

$p \times q-1$$k \geq 2$$k$

$p \times q-1$$k$$2$ Netze behandelt). Daher ist dies keine vollständige Antwort. Es ist auch enttäuschend, dass sie keine Referenzen enthalten, wenn sie behaupten, dass das Problem noch offen ist.