NP - Completude do problema de decisão para os 15 quebra-cabeças generalizados

Estou interessado na generalização natural do famoso quebra-cabeça 15 , onde você tem que deslizar os blocos até classificar todos os números (geralmente existe uma diferença de 1 bloco).

Agora, a generalização seria estender o tamanho do quebra-cabeça de 15 para , onde um campo está livre. Eu criei uma pequena ilustração (as setas tracejadas mostram movimentos permitidos e a configuração inferior mostra o quebra-cabeça resolvido):$p \times q$

Dada a configuração inicial de um quebra-cabeça, eu me faço a seguinte pergunta:

Questão de decisão : Dado um quebra-cabeça de tamanho e um número . Existe uma sequência de movimentos ou menos permitidos que transformam o quebra-cabeça na configuração resolvida?k ∈ N$p \times q$$k \in \mathbb{N}$$k$

Eu já fiz alguma investigação e encontrei o artigo " O enigma e os problemas de realocação relacionados$(n^2−1)$ " de 1990, que mostram que decidir minha pergunta para é NP-Completo e, portanto, decidir minha pergunta é NP -Completo (como o algoritmo geral também pode decidir a questão dos campos simétricos).$p=q$

A questão que permanece em aberto é se o problema de decisão também é NP-Complete para fixo . Estou particularmente interessado nos casos especiais . Ele também permanece aberto se permitir mais espaços livres do que um campo tornar o problema de decisão mais difícil ou mais fácil.q = 2 , $q>1$$q=2,3$

Infelizmente, todos os artigos que pude encontrar omitem o caso assimétrico, portanto acho que talvez não haja resultados conhecidos sobre isso. Como a prova no artigo é bastante complicada e não se traduz em altura fixa, espero que alguém possa apresentar uma redução / artigo diferente que responda a algumas perguntas.

Outros artigos relacionados (a serem estendidos):

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

Acho que encontrei uma resposta parcial (embora bastante decepcionante) para o meu problema:

Eu tropecei neste artigo (2007):

" A complexidade do roteamento tridimensional de canais ", de Satoshi Tayu e Shuichi Ueno

Eles mostram (Teorema 4) que o com "2-redes" e dimensão de "encaminhamento problema 3d-canal" pode ser resolvido, se e apenas se o (artigo de verificação para mais detalhes) correspondente enigma lata ser resolvido.p × q - $p,q$$p \times q-1$

$k$$k \geq 2$

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

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