NP-Kompletność problemu decyzyjnego dla uogólnionego 15-puzzle

Interesuje mnie naturalne uogólnienie słynnej 15-puzzli , w których musisz przesuwać bloki, dopóki nie posortujesz wszystkich podanych liczb (zwykle jest przerwa 1 blok).

Teraz uogólnieniem byłoby zwiększenie rozmiaru układanki z 15 do , gdzie jedno pole jest wolne. Stworzyłem małą ilustrację (przerywane strzałki pokazują dozwolone ruchy, a dolna konfiguracja pokazuje rozwiązaną łamigłówkę):$p \times q$

Biorąc pod uwagę początkową konfigurację układanki, zadaję sobie następujące pytanie:

Pytanie decyzyjne : Biorąc pod uwagę układankę wielkości oraz liczbę . Czy istnieje sekwencja lub mniej dozwolonych ruchów, które przekształcają układankę w rozwiązaną konfigurację?k ∈ N$p \times q$$k \in \mathbb{N}$$k$

Przeprowadziłem już pewne dochodzenie i znalazłem artykuł „ The -puzzle i powiązane problemy$(n^2−1)$ z relokacją ” z 1990 roku, który pokazuje, że rozstrzygnięcie mojego pytania dla jest NP-Complete, a zatem to, że moje pytanie jest NP -Kompletne (ponieważ ogólny algorytm może również decydować o pytaniu dla pól symetrycznych).$p=q$

Pozostaje otwarte pytanie, czy problem decyzyjny jest również NP-Complete dla ustalonego . Szczególnie interesują mnie przypadki szczególne . Pozostaje również otwarty, jeśli zezwolenie na więcej wolnych miejsc niż jedno pole utrudnia lub ułatwia podejmowanie decyzji.q = 2 , $q>1$$q=2,3$

Wszystkie artykuły, które udało mi się znaleźć, niestety pomijają przypadek asymetryczny, dlatego myślę, że mogą nie być znane żadne wyniki na ten temat. Ponieważ dowód w artykule jest dość skomplikowany i w ogóle nie tłumaczy się na ustaloną wysokość, mam raczej nadzieję, że ktoś może wymyślić inną redukcję / artykuł, który odpowiada na niektóre pytania.

Inne powiązane artykuły (do rozszerzenia):

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

Myślę, że znalazłem częściową (choć dość rozczarowującą) odpowiedź na mój problem:

Natknąłem się na ten artykuł (2007):

„ Złożoność trójwymiarowego trasowania kanałów ” autorstwa Satoshi Tayu i 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$