O Hidoku NP está completo?

Um Hidoku é uma grade com alguns números inteiros pré-preenchidos de 1 a . O objetivo é encontrar um caminho de números inteiros sucessivos (de 1 a ) na grade. Mais concreto, cada célula da grade deve conter um número inteiro diferente de 1 a e cada célula com valor deve ter uma célula vizinha com valor (também pode ser na diagonal). $n \times n$ $n^2$ $n^2$ $n^2$ $z ≠ n^{2}$ $z + 1$

É NP difícil decidir se um Hidoku é solucionável? Que redução poderia ser usada?

Edit: de acordo com os comentários, dou um pequeno esclarecimento. Dada a grade de células, algumas delas já contêm valores (números inteiros de 1 a n²). Devemos preencher todas as células restantes com números inteiros de 1 a , de modo que não haja duas células com o mesmo valor e que cada célula com valor tenha um vizinho com valor . Ou seja, depois de preencher as células, devemos encontrar o caminho . Na grade, que visita logicamente cada célula. $n^2$ $z ≠ n²$ $z + 1$ $1, 2, 3,\cdots, n^2$

Um exemplo de um Hidoku seria http://www.janko.at/Raetsel/Hidoku/018.c.gif . Um Hidoku já resolvido é http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , onde você pode ver o caminho ao qual eu estava me referindo.

complexity-theory reductions np-hard ipsec
fonte

Intuitivamente, sem pensar muito nisso, soa polytime solucionável à primeira vista. Algo como programação dinâmica nos valores permitidos ( ) e nos vértices ( ). Soa solucionável no tempo .

1, \dots, n^{2}

$1, \dots, n^2$

v_{1}, \dots v_{n}

$v_1, \dots v_n$

O (n^{3})

$O(n^3)$

precisa

Isto pode ser modelado como equivalentemente gráfico, a ligação dos nós com bordas se eles são sucessores em

. Então, você está procurando um caminho de Hamilton. De acordo com os caminhos de Hamilton nos gráficos de grade de Itai et al. (1982) esse problema é NP-completo em gráficos de grade. Isso não se ajusta imediatamente ao seu problema, pois você permite conexões diagonais, mas é um mau presságio.

N

$\mathbb{N}$

Raphael

@Raphael não é o gráfico construído um DAG?

Pål GD

Não vejo como isso é um DAG. Pelo que entendi, a entrada é um gráfico de grade (não direcionado) (contendo também bordas diagonais) e o objetivo é encontrar um caminho hamiltoniano, onde é dada a posição de alguns nós no caminho.

George

@ George Okey, interpretei a pergunta como encontrar o caminho máximo para aumentar os valores em uma grade!

Pål GD

Respostas:

Penso que é -completo: como notado por Raphael, ciclo hamiltoniano em gráficos de grelha com furos problema é NP-completo ( Alon Itai, Christos Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Caminhos em grade Gráficos SIAM J. Comput.. 11 (4): 676-686 (1982) ). $\sf{NP}$

Assim, dado um gráfico de grade com furos, você pode facilmente criar um jogo Hidoku equivalente, onde as células fixas iniciais preenchem todas as diagonais pares; as diagonais ímpares vazias formam um gráfico não direcionado equivalente ao gráfico de grade original e o Hidoku tem uma solução se e somente se o gráfico de grade original tiver um caminho hamiltoniano. $G$ $G$

insira a descrição da imagem aqui

Figura 1: um gráfico de grade com furos e o quebra-cabeça equivalente Hidoku (células azuis representam as células numeradas fixas iniciais ( é a primeira, é a última), células brancas são as células que o jogador deve preencher, linha roxa indica a sequência das células numeradas fixas iniciais). $12 \times 12$ $1$ $144$

Linhas auxiliares (preenchidas) podem ser adicionadas ao lado inferior ou direito para torná-lo um quadrado.

Outro exemplo de redução de um gráfico de grade para um quebra-cabeça Hidoku: o gráfico de grade 6x4 é incorporado em uma grade 13x13 maior; as diagonais pares são preenchidas com números fixos e as células livres restantes são equivalentes ao gráfico de grade original.

insira a descrição da imagem aqui

A imagem completa com a transformação pode ser baixada aqui .

Algumas notas adicionais para completar a resposta:

o problema também é conhecido como Hidato ; a placa pode ter uma forma arbitrária (mas, como generalização da caixa quadrada, ela permanece NP-hard);
como corretamente evidenciado por Steven Stadnicki em sua resposta não é óbvio que o problema está em NP se a grade inicial parcialmente preenchido não é dado como um array de inteiros, mas é dada em alguns sucinta representação; no entanto, é claramente em NP se o quadro inicial é fornecido usando a lista razoável de representação de números inteiros; $n \times n$
Eu acho que as regras originais do jogo dizem que a solução deve ser única ; então o problema está nos EUA (difícil nos EUA ) e é improvável que esteja no NP.

$n^2$ $\sf{NP}$

Vor
fonte

Isso não é um DAG? Eu entendi completamente a pergunta?

Pål GD

@ PålGD: não, não acho que seja um DAG, é um gráfico de grade sem direção com bordas diagonais. O jogo começa com um tabuleiro parcialmente cheio e o jogador deve começar a partir da célula 1 e chegar ao último fazendo etapas ortogonais ou diagonais (mas talvez eu não lembre as regras muito bem ... agora eu verifiquei)

Vor

Mas diz "encontre um caminho de números inteiros sucessivos".

Pål GD

Talvez isso simplesmente significa que ele não pode visitar o mesmo celular duas vezes, e que todas as células devem ser visitados

Vor

1

$1$

n^{2}

$n^2$

$n\times n$ $\Omega(n)$ $n$ $\lg n$ $(x_i, y_i, w_i): x_i, y_i\leq n, w_i\leq n^2$ $(x_i, y_i)$ $w_i$ $\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$ $\Omega(n)$ $o(n)$

$\Omega(n)$

(Para uma discussão de questões semelhantes, veja minha pergunta sobre a complexidade de um sucinto Nurikabe no site cstheory.SE.)

Steven Stadnicki
fonte

Não especificar o tamanho da placa em unário me parece uma interpretação irracional.

David Eisenstat

@DavidEisenstat Não é necessariamente a interpretação natural , mas parece perfeitamente válida para mim.

Steven Stadnicki

@StevenStadnicki: Concordo com você. Fiz uma anotação semelhante na prova de completude de NP do Binary Puzzle, que publiquei recentemente em cstheory.stackexchange.com. Embora a representação não unária não seja de fato tão razoável :-). Vou adicionar uma nota na minha resposta. E também devo abordar o problema da singularidade da solução; porque acho que as regras originais dizem que a solução deve ser única.

Vor