NP-Kelengkapan masalah keputusan untuk 15-puzzle umum

Saya tertarik pada generalisasi alami dari 15-puzzle yang terkenal , di mana Anda harus menggeser blok sampai Anda telah mengurutkan semua angka yang diberikan (biasanya ada celah 1 blok).

Sekarang generalisasi akan memperluas ukuran puzzle dari 15 ke , di mana satu bidang gratis. Saya telah membuat ilustrasi kecil (panah putus-putus menunjukkan gerakan yang diizinkan dan konfigurasi yang lebih rendah menunjukkan teka-teki yang diselesaikan):$p \times q$

Diberikan konfigurasi awal teka-teki, saya bertanya pada diri sendiri pertanyaan berikut:

Pertanyaan keputusan : Diberikan puzzle ukuran , dan angka . Apakah ada urutan gerakan atau kurang diizinkan yang mengubah teka-teki menjadi konfigurasi terpecahkan?k ∈ N$p \times q$$k \in \mathbb{N}$$k$

Saya sudah melakukan beberapa penyelidikan dan menemukan artikel " Masalah -tabung dan masalah relokasi terkait$(n^2−1)$ p = q " dari tahun 1990, yang menunjukkan bahwa memutuskan pertanyaan saya untuk adalah NP-Lengkap dan oleh karena itu yang memutuskan pertanyaan saya adalah NP -Lengkap (seperti algoritma umum juga bisa memutuskan pertanyaan untuk bidang simetris).$p=q$

Pertanyaan yang tetap terbuka adalah apakah masalah keputusan juga NP-Complete untuk fixed . Saya khususnya tertarik pada kasus-kasus khusus . Itu juga tetap terbuka jika memungkinkan lebih banyak ruang bebas dari satu bidang membuat masalah keputusan lebih sulit atau lebih mudah.q = 2 , $q>1$$q=2,3$

Semua artikel yang saya temukan dengan sedih dapat menghilangkan kasus asimetris, jadi saya pikir mungkin tidak ada hasil yang diketahui tentang hal ini. Karena buktinya dalam artikel ini cukup rumit dan tidak menerjemahkan sama sekali untuk ketinggian tetap, saya lebih berharap bahwa seseorang mungkin datang dengan pengurangan / artikel berbeda yang menjawab beberapa pertanyaan.

Artikel terkait lainnya (akan diperpanjang):

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

Saya pikir saya menemukan jawaban parsial (meskipun cukup mengecewakan) untuk masalah saya:

Saya sengaja menemukan makalah ini (2007):

" Kompleksitas Routing Saluran Tiga Dimensi " oleh Satoshi Tayu dan 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$