Obter dois de um

12

Como vimos nesta questão , declarações lógicas complexas podem ser expressas em termos dos conectivos simples do Campo Minado generalizado. No entanto, o caça-minas generalizado ainda possui redundâncias.

Para evitar essas redundâncias, definimos um novo jogo chamado "Generalized-1 Minesweeper".

O Campo Minado Generalizado-1 é uma versão do Campo Minado reproduzida em um gráfico arbitrário. O gráfico possui dois tipos de vértice, um "indicador" ou um "valor". Um valor pode ser ativado ou desativado (uma mina ou um insucesso), porém seu estado é desconhecido para o jogador. Um indicador informa que exatamente uma das células adjacentes está ligada (uma mina). Os indicadores não contam como minas.

Por exemplo, a seguinte placa para o Campo Minado Generalizado nos diz que as células A e B são minas ou nenhuma delas.

Jogo simples

(No diagrama, os indicadores são marcados em cinza enquanto os valores são em branco)

Diferente do caça-minas normal, em que você clica nos valores que estão desativados para revelar indicadores, não existe esse mecânico no caça-minas generalizado. Um jogador simplesmente determina para quais estados do gráfico podem satisfazer seus indicadores.

Seu objetivo é fazer um 2caça-minas generalizado-1. Você criará uma estrutura no Generalized-1 Minesweeper, de modo que haja 8 células específicas para as quais todas as configurações possíveis de valores tenham exatamente duas células ativadas. Isso significa que ele se comporta exatamente como o 2faz no tradicional caça-minas. Ao escrever sua solução, você não deve ter valores específicos em mente para células de valor. (Em resposta à pergunta de H.PWiz, é permitido que algumas células de valor possam ser dedutíveis do estado)

Pontuação

Suas respostas serão pontuadas pelo número de vértices no gráfico final menos 8 (para as 8 entradas), com uma pontuação menor sendo melhor. Se duas respostas estiverem vinculadas nessa métrica, o desempate será o número de arestas.

Post Rock Garf Hunter
fonte
Alguma aresta sempre conecta um vértice indicador e um vértice de valor?
xnor
@xnor Para maximizar sua pontuação, eles deveriam, mas não acho que preciso fazer disso uma regra. Bordas que não conectam valores a indicadores não alteram o comportamento do gráfico.
Post Rock Garf Hunter
Quando 6 é subtraído da pontuação, quais são as 6 entradas? Não existem 8 células?
xnor
@xnor Desculpe, deveria ser 8. Corrigido agora.
Post Rock Garf Hunter
O que você quer dizer com "estrutura ... de tal forma que existem 8 células específicas nas quais as únicas configurações possíveis de valores têm exatamente duas células ativadas". As únicas configurações possíveis deveriam ter apenas duas minas?
dylnan 31/01

Respostas:

7

42 vértices, 56 arestas

Rede de minas

Cada variável é um vértice de valor e cada caixa é um vértice indicador com arestas para as variáveis ​​dentro dela. As entradas são x 1 , ..., x 8 . Por exemplo, aqui está uma solução com minas em x 3 e x 5 , com as minas destacadas em verde.

Solução de rede de minas

As restrições horizontais garantir que exatamente um dos um 's e exatamente um dos b ' s tem uma mina. Nessas duas colunas, r não possui uma mina, mas nas outras seis colunas. (Note-se que um e b não podem ambos ter uma mina na mesma coluna). Cada entrada x é oposta a R na sua coluna, de modo exactamente duas entradas tem minas como desejado.

Para kentradas, isso usa 5k+2vértices ( 3kvalor e 2k+2indicador) e 7karestas. Aqui, as k=8entradas fornecem 42 vértices e 56 arestas.

xnor
fonte
3

50 vértices, 89 arestas

Baseado no portão lógico da resposta de H.PWiz.

  A&B      C&D      E&F      G&H
   |        |        |        |
b--1--a  d--1--c  f--1--e  h--1--g
|  |  |  |  |  |  |  |  |  |  |  |
1--?--1  1--?--1  1--?--1  1--?--1
|     |  |     |  |     |  |     |
A     B  C     D  E     F  G     H

Cada um *está ativado quando as duas entradas respectivas estão ativadas. Para lidar com o caso de uma única entrada, usamos os valores intermediários a=A&!Betc. conectar todos os três valores a, be A&Bà entrada de um nível secundário de portões nos dá uma entrada eficaz de A|B(isso poupa vértices mais !(!A&!B)):

      *              *
      |              |
   #--1--#        #--1--#
   |  |  |        |  |  |
   1--?--1        1--?--1
  |||   |||      |||   |||
  A|B   C|D      E|F   G|H

Estes *estão ativados se duas de suas entradas (correspondentes a quatro das entradas originais) estiverem ativadas, exceto no caso dos pares já abordados acima. Enquanto isso, podemos conectar os #*#nós a um portão final. Portanto, temos os seguintes resultados:

A&B
C&D
E&F
G&H
(A|B)&(C|D)         [4 cases]
(E|F)&(G|H)         [4 cases]
(A|B|C|D)&(E|F|G|H) [16 cases]

Estes abrangem todos os 28 casos de duas entradas. Resta então conectar um indicador final a esses sete valores. Se menos de duas entradas estiverem ativadas, nenhuma delas estará ativada, portanto o indicador estará desligado. Se mais de duas entradas estiverem ativadas, mais de uma delas estará ativada e o indicador apagado.

Neil
fonte
Ah, eu tive uma idéia semelhante, mas acabei criando uma versão mais complicada disso. Bom trabalho!
justhalf
Não estou convencido de que existem 43 vértices. Você mostra claramente 42, então está dizendo que só precisa de mais uma para conectar tudo?
21418 H.PWiz
Na verdade, se eu ter desenhado corretamente o gráfico que você descreve, eu acho que ele permite a estados como ACE, BDF, ADG...
H.PWiz
@ H.PWiz Entendo o que você quer dizer ... acho que talvez eu possa resolver isso com arestas extras para dar a expressão (a&b)+((a|b)&(c|d))+(c&d)+((a|b|c|d)&(e|f|g|h))+(e&f)+((e|f)&(g|h))+(g&h)==1, isso parece certo para você?
Neil
Talvez, embora para mim essa expressão pareça resolver o problema completamente. E eu não tenho idéia do que bordas você pode adicionar para obter essa ...
H.PWiz
2

197 vértices, 308 arestas

Eu vim com essa resposta ontem à noite, mas retive a postagem porque era uma pontuação muito alta. No entanto, uma vez que supera a outra resposta por tantas, acho que devo publicá-la.

Eu uso o seguinte configurado em todos os 28 pares de células de valores em ABCDEFGH

   ?*
   |
?--1--?
|  |  |
1--?--1
|     |
A     B

?representa uma célula de valor que não está ABCDEFGH. Aqui, quando ?*é ON , Ae Bsão ambos diante. Caso contrário, Ae Bpode estar em qualquer outra configuração.

Eu conecto todos os 28 ?*s em uma célula indicadora. Isso significa que apenas um par ABCDEFGHterá dois ON . O que é suficiente para garantir que exatamente duas das minhas células de saída estejam LIGADAS

H.PWiz
fonte
1
Observe que no portão você tem cada um dos 4 ?s corresponde a um dos 4 estados de A B.
Post Rock Garf Hunter
@HeebyJeebyMan Interessante, eu não tinha considerado isso. Eu encontrei esta porta por sorte
H.PWiz
1

354 nós, 428 arestas

Só para provar que é possível. Melhorarei isso mais tarde com algum cache.

(espero que não haja erro de código)

Tentei escrever um programa Mathematica aqui para verificar a validade do programa, mas provavelmente não funciona porque existem muitas variáveis.

O resultado foi gerado por programa de computador: Experimente online!


Eu uso um portão que se parece com isso:


               (f)
                |
                |
               (#)
              /   \
             /     \
           (d)     (e)
          /           \
         /             \
       (#) --- (c) --- (#)
     .'                  '.
   .'                      '.
(a)                          (b)

onde (#)são 1 indicadores, (a).. (f)são valores.

Então,


c = (not a) and (not b)
d = (not a) and      b
e =      a  and (not b)
f =      a  xnor     b

Além disso, este portão


(a) ----- (#) ----- (b)


b = not a

. Use esses dois tipos de portas que você pode construir quaisquer expressões.

Obviamente, este é para afirmar que (a)deve ser verdade:


(a) ----- (#)
user202729
fonte
1

81 nós, 108 bordas

Usando 13 nós e 14 arestas, criamos o seguinte gate Adder (C (arry) = X AND Y, S (um) = X XOR Y):

X - 1 --------------?
   | |
   ? - 1 - S - 1 -? - 1
   | | |
   | C
Y - 1 --------------?

Use quatro Adicionadores M1, M2, M3, M4 para adicionar A + B, C + D, E + F, G + H, respectivamente, com o transporte C1, C2, C3, C4 resultante e a soma S1, S2, S3, S4

Use dois Adicionadores M5, M6 para adicionar S1 + S2, S3 + S4, com o transporte C5, C6 resultante e a soma S5, S6.

Use um Adder M7 para adicionar S5 + S6 para obter C7 e S7.

Agora, conecte todos os carregamentos a um único nó indicador, como o seguinte:

C1-
C2-
C3-
C4 - + - 1
C5-
C6-
C7-

e forçar S7 (o módulo 2 da soma de 8 valores) a ser 0 por este circuito:

S7--1 -? - 1

Argumento que esse circuito força exatamente dois valores ABCDEFGHpara estarem LIGADOS, pois só pode ser um número par (já que S7 é 0) e não pode haver mais de 3 valores LIGADOS (já que apenas um de C1-C7 está LIGADO).

justhalf
fonte