Este jogo clássico de livro de quebra-cabeças está completo com NP?

Existe um jogo clássico de livro de quebra-cabeças muito semelhante a um jogo de palavras cruzadas, exceto que uma lista de palavras é fornecida e, em seguida, é fornecido um tabuleiro composto por quadrados unitários, com alguns quadrados apagados como uma palavra cruzada, e alguns quadrados já possuem uma carta pré-escrita. O objetivo é escrever cada palavra da lista uma vez e apenas uma vez no quebra-cabeça, onde cada palavra é escrita horizontalmente (da esquerda para a direita) ou verticalmente (de cima para baixo) em quadrados consecutivos não apagados e quando você escreve uma palavra , os dois quadrados que flanqueiam as extremidades da palavra devem estar apagados ou fora do quadro. Também para as letras pré-escritas em alguns quadrados, as palavras escritas que se sobrepõem a esses quadrados devem respeitar a letra pré-escrita.$N \times N$

Agora, se assumirmos um alfabeto de tamanho fixo para as palavras, está decidindo se podemos preencher o quadro com uma solução válida usando exatamente cada palavra da lista uma vez e apenas uma vez um problema de NP-completo, se o comprimento lateral do quadro for não consertado?

Desculpe por responder uma postagem antiga.

Eu estive pensando sobre isso e acho que o problema com um alfabeto fixo também é NP-completo.

Vou reduzir 1-em-3 SAT positivo para esse problema de palavra

Ontem eu estava tendo problemas para apresentar idéias para resolver o problema. Eu tive problemas para diferenciar cada variável até que olhei novamente para a pergunta e percebi que você permitia ter quadrados com símbolos plantados. Isso simplificou muito a redução. Minha outra idéia era ter palavras de comprimento diferente para cada variável diferente.

A REDUÇÃO

Agora vou descrever os gadgets que vamos usar:

Gadget variável

Rotulamos cada variável com um índice numérico diferente e teremos um número diferente para cada variável. Nós escolhemos o maior índice e representamos o número em binário, chamaremos essa cadeia binária .$n$

Em seguida, criamos duas palavras verticais diferentes para cada variável. Todas as palavras terão um comprimento de(Somente se permitirmos palavras duplicadas na lista de palavras), ondeé o comprimento da cadeia binária n .| n $3 + |n|$$|n|$$n$

Por exemplo, permita que o maior índice seja o número . Quando transformamos esse número em binário, obtemos a cadeia 100 em binário, essa cadeia tem um comprimento de três. Portanto, cada palavra variável terá um comprimento de 6 neste exemplo.$4$$100$$6$

Agora criamos duas palavras diferentes para cada variável. Uma palavra terá o símbolo no início, depois o símbolo 2 abaixo e, em seguida, uma cadeia binária que representa o índice da variável e zeramos a cadeia para que ela tenha o mesmo comprimento que a cadeia n e, finalmente, o símbolo 3 no fim. Claro que os símbolos podem ser alterados.$3$$2$$n$$3$

A outra palavra é quase a mesma, mas terá o símbolo vez do símbolo 3 .$4$$3$

Por exemplo, permita que o maior índice seja o número . Teremos as seguintes duas palavras para a variável com o índice 1 :$4$$1$

e$320013$$420014$

Como vemos, aumentamos a reperesentação binária do número com zeros, para que ele tenha um comprimento de | n $1$$|n|$

Temos que copiar essas palavras muitas vezes, precisaremos de uma cópia de cada palavra para cada ocorrência de uma variável na instância SAT. Isso criará duplicatas na lista de palavras. Podemos nos livrar das duplicatas adicionando outra cadeia binária à cadeia binária que identifica exclusivamente a variável. Essa nova cadeia identificará exclusivamente cada ocorrência de uma variável.

Para fazer isso, simplesmente atribuímos a cada ocorrência da variável outra cadeia binária e definimos essa cadeia no final da representação binária da variável.

Para criar pela primeira vez esta nova cadeia binária temos que criar um índice diferente para cada variável, chamamos o maior número em cada índice , onde i é um identificador para cada variável. Depois disso, transformamos o número n i em uma cadeia binária e depois contamos o comprimento da cadeia, chamamos esse número | n eu | . Em seguida, para cada índice, criamos um número binário diferente para cada ocorrência da variável. Retornamos o número com zeros até que o comprimento da cadeia binária se torne | n eu | para que todas as palavras que pertencem a cada ocorrência da variável tenham o mesmo comprimento.$n_i$$i$$n_i$$|n_i|$$|n_i|$

Isso eliminará duplicatas dentro das palavras variáveis.

Por exemplo, suponha que a variável apareça três vezes na instância SAT. Criamos as seguintes palavras:$x_2$

42010014 , 32010103 42010104 e 32010113 $32010013$ $42010014$$32010103$ $42010104$$32010113$ $42010114$

Gadget de cláusula

Para cada gadget de cláusula, criaremos três novas palavras horizontais, cada palavra de cláusula terá um comprimento de quadrados (somente se permitirmos palavras duplicadas na lista de palavras). Estas são as palavras que criaremos para cada cláusula:$6$

, 535453 e$535354$$535453$$545353$

Temos uma palavra de cláusula diferente para cada maneira possível de satisfazer a cláusula, o símbolo representa um conjunto literal como verdadeiro e o símbolo 3 representa um conjunto literal como falso. O número 5 é usado para indicar que é uma palavra de cláusula.$4$$3$$5$

Haverá palavras repetidas na lista de palavras. Podemos nos livrar das repetições usando o procedimento que usamos para identificar exclusivamente as palavras variáveis. Ou seja, criamos uma cadeia binária diferente para cada cláusula e anexamos cada cadeia às palavras da cláusula correspondentes a cada cláusula. Para isso, criamos um novo índice para as cláusulas e escolhemos o maior número do índice, chamaremos esse número de . Representamos m como uma cadeia binária e chamamos o comprimento dessa cadeia binária como | m | . Agora, criamos um número binário diferente para cada cláusula, começando com o número 1, e preenchemos o número com zeros para criar uma cadeia binária que tenha um comprimento de | m $m$$m$$|m|$$|m|$. Anexamos cada cadeia binária às palavras da cláusula que pertencem à cláusula.

Agora, vamos ver uma imagem de um gadget de cláusula no quadro:

Este exemplo representa a cláusula e do exemplo 1 em 3 a ser reduzida é ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 2 ∨ x 3 ∨ x 4$(x_2 \lor x_3 \lor x_4)$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Como vemos, existem quadrados escritos. As colunas verticais têm símbolos escritos para indicar quais literais estão dentro da cláusula. O final e o início da coluna são quadrados em branco. Isso permite que o jogador escolha o valor da variável. Os símbolos marcados na linha horizontal forçam o jogador a colocar uma palavra de cláusula nessa linha. Como todas as palavras da cláusula têm apenas um único símbolo significa que apenas um dos literais que estão dentro do gadget da cláusula pode ser definido como "true".$4$

Se não permitirmos duplicatas dentro da lista de palavras, teremos que modificar a imagem.

A linha da cláusula na imagem se tornará: e as colunas literais serão, da esquerda para a direita:$5b5b5b10$

, b 201110 b e b 21,001 $b201010b$$b201110b$$b21001b$

Onde o símbolo significa quadrado em branco$b$

Veja um exemplo:

Gadget de consistência variável

Este é um gadget que garante que o player possa atribuir apenas o mesmo valor a todas as colunas literais de uma variável.

Teremos um novo gadget para cada variável

Criaremos duas novas palavras para cada gadget.

O comprimento da palavra dependerá do número de ocorrências de uma variável. O comprimento de uma palavra será onde k é o número de ocorrências de uma variável. Portanto, se a variável x 2 aparecer duas vezes na instância sat, as palavras terão um comprimento de quatro. Uma das duas palavras é formada repetindo a cadeia 63 k vezes, em que k é o número de ocorrências da variável. A outra palavra é formada repetindo a cadeia 64 k vezes, em que k é o número de ocorrências da variável na instância SAT sendo reduzida.$2 * k$$k$$x_2$$63$ $k$$64$ $k$

$x_2$

$6363$$6464$

Se quisermos evitar palavras repetidas, observe que cada gadget de consistência pertence a uma variável diferente. Portanto, podemos acrescentar a cadeia binária que identifica cada variável às duas palavras que criamos para esse gadget.

Agora vamos ver uma imagem de exemplo deste gadget:

$x_2$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

$3$$4$$3$$4$. Podemos colocar a palavra restante desse gagdet na outra linha

Se não permitirmos duplicatas na lista de palavras, as palavras dentro da figura de exemplo serão:

Para as linhas:

$6b6b010$$6b6b010$

Para as colunas:

$b201001b$$b201010b$

Onde o símbolo b$b$

Veja um exemplo:

Gadget de despejo de cláusula

Este é um gadget criado para colocar as palavras de cláusula não utilizadas. Para fazer isso, basta colocar duas linhas para cada palavra de cláusula em uma parte vazia do quadro. Essas linhas não estão conectadas a nenhuma outra linha ou coluna.

Com isso, finalizamos a redução, pois alegamos que precisamos apenas de 6 símbolos para a redução.

Exemplo

Se a explicação anterior foi confusa, aqui está um exemplo de exemplo de uma instância de 1 em 3 SAT positivo que foi reduzido a esse problema de palavra:

Se não permitirmos palavras repetidas:

A instância que foi reduzida é:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Eu acho que a seguinte redução do caminho Hamiltoniano Direcionado funciona:

$G=(V,E)$$s,t\in V$

$V\cup \{*\}$$*$$V$

$v*v$$v\in V$$vu$$(u,v)\in E$

$|V|$

$|E|-(|V|-1)$

$s*s$$t*t$

Agora, para preencher as escadas, apenas palavras de vértice podem ser colocadas dentro das etapas e, para conectar dois vértices, uma palavra de aresta deve ser colocada entre elas, o que corresponde a uma aresta existente no gráfico. As arestas não utilizadas podem ser colocadas na segunda parte do quadro. A segunda direção é trivial.

Eu acho que isso funciona (a prova de correção que eu esbocei é ondulada à mão, na melhor das hipóteses, mas ainda assim).