Consigue dos de uno

12

Como vimos en esta pregunta , las declaraciones lógicas complejas se pueden expresar en términos de los conectivos simples del Buscaminas generalizado. Sin embargo, el buscaminas generalizado todavía tiene redundancias.

Para evitar estas redundancias, definimos un nuevo juego llamado "Generalized-1 Minesweeper".

Generalized-1 Minesweeper es una versión que Minesweeper jugó en un gráfico arbitrario. El gráfico tiene dos tipos de vértice, un "indicador" o un "valor". Un valor puede estar activado o desactivado (una mina o un fracaso), sin embargo, su estado es desconocido para el jugador. Un indicador indica que exactamente una de las celdas adyacentes está encendida (una mina). Los indicadores no cuentan como minas en sí.

Por ejemplo, la siguiente tabla para el Buscaminas generalizado nos dice que las celdas A y B son minas o ninguna de ellas son minas.

Juego simple

(En el diagrama, los indicadores están marcados en gris mientras que los valores son blancos)

A diferencia del dragaminas normal donde hace clic en los valores que están apagados para revelar indicadores, no existe tal mecánica en el Buscaminas generalizado. Un jugador simplemente determina qué estados del gráfico pueden satisfacer sus indicadores.

Tu objetivo es hacer un 2Buscaminas generalizado-1. Construirá una estructura en el Buscaminas generalizado-1 de modo que haya 8 celdas específicas para las que todas las configuraciones posibles de valores tengan exactamente dos celdas. Esto significa que se comporta exactamente como lo 2hace en el buscaminas tradicional. Cuando escribe su solución, no debe tener en cuenta valores específicos para las celdas de valores. (En respuesta a la pregunta de H.PWiz, se permite que algunas celdas de valor sean deducibles del estado)

Puntuación

Sus respuestas se puntuarán por el número de vértices en el gráfico final menos 8 (para las 8 entradas) con una puntuación más baja mejor. Si dos respuestas empatan en esta métrica, el separador será el número de bordes.

Ad Hoc Garf Hunter
fuente
¿Alguna arista siempre conecta un vértice indicador y un vértice de valor?
xnor
@xnor Para maximizar su puntaje deberían, pero no creo que tenga que hacer que sea una regla. Los bordes que no conectan valores a los indicadores no cambian el comportamiento del gráfico.
Ad Hoc Garf Hunter
Cuando se resta 6 del puntaje, ¿cuáles son las 6 entradas? ¿No hay 8 celdas?
xnor
@xnor Lo siento debería ser 8. Corregido ahora.
Ad Hoc Garf Hunter
¿Qué quiere decir con "estructura ... de modo que hay 8 celdas específicas en las que las únicas configuraciones de valores posibles tienen exactamente dos celdas"? ¿Se supone que las únicas configuraciones posibles tienen solo dos minas?
dylnan

Respuestas:

7

42 vértices, 56 bordes

Red de minas

Cada variable es un vértice de valor, y cada cuadro es un vértice indicador con bordes a las variables dentro de él. Las entradas son x 1 , ..., x 8 . Por ejemplo, he aquí una solución con minas en x 3 y x 5 , con minas resaltados en verde.

Solución de red de minas

Las restricciones horizontales aseguran que exactamente una de las a 's y exactamente una de las b ' s tenga una mina. En esas dos columnas, r no contiene una mina, pero sí en las otras seis columnas. (Tenga en cuenta que una y b no se puede tener tanto una mina en la misma columna.) Cada entrada x está enfrente de la r en su columna, de modo exactamente dos entradas tienen minas según se desee.

Para las kentradas, esto usa 5k+2vértices ( 3kvalor e 2k+2indicador) y 7karistas. Aquí, las k=8entradas dan 42 vértices y 56 aristas.

xnor
fuente
3

50 vértices, 89 bordes

Basado en la puerta lógica de la respuesta 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 uno *está activado cuando las dos entradas respectivas están activadas. Para manejar el caso de una sola entrada, se utilizan los valores intermedios a=A&!Betc. Conexión los tres valores a, by A&Ba la entrada de un nivel secundario de puertas nos da una entrada eficaz de A|B(esto ahorra vértices más de !(!A&!B)):

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

Estos *s están activados si dos de sus entradas (correspondientes a cuatro de las entradas originales) están activadas, excepto en el caso de los pares ya cubiertos anteriormente. Mientras tanto, podemos conectar los #*#nodos a una puerta final. Por lo tanto, tenemos los siguientes 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]

Estos cubren los 28 casos de dos entradas. Entonces queda por conectar un indicador final a estos siete valores. Si hay menos de dos entradas encendidas, ninguna de ellas estará encendida, por lo que el indicador estará apagado. Si hay más de dos entradas encendidas, más de una de ellas estará encendida y el indicador estará apagado.

Neil
fuente
Ah, tuve una idea similar, pero terminé creando una versión más complicada de esto. ¡Buen trabajo!
solo
No estoy convencido de que haya 43 vértices. ¿Muestra claramente 42, entonces está diciendo que solo necesita uno más para conectarlo todo?
H.PWiz
En realidad, si he dibujado correctamente la gráfica que describe, creo que permite estados como ACE, BDF, ADG...
H.PWiz
@ H.PWiz Ya veo lo que quieres decir ... Creo que tal vez pueda resolver eso con bordes adicionales para dar la expresión (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, ¿te parece correcto?
Neil
Tal vez, aunque para mí esa expresión parece resolver el problema por completo. Y no tengo idea de qué bordes puedes agregar para obtener eso ...
H.PWiz
2

197 vértices, 308 bordes

Anoche se me ocurrió esta respuesta, pero no la publiqué porque era una puntuación muy alta. Sin embargo, dado que supera mucho a la otra respuesta , pensé que debería publicarla.

Utilizo la siguiente configuración en los 28 pares de celdas de valores en ABCDEFGH

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

?representa una celda de valor que no está en ABCDEFGH. Aquí, cuando ?*está ENCENDIDO , Ay Bambos están encendidos. De lo contrario, Ay Bpodría estar en cualquier otra configuración.

Conecto los 28 ?*s a una celda indicadora. Esto significa que solo un par ABCDEFGHtendrá dos ON . Lo cual es suficiente para exigir que exactamente dos de mis celdas de salida estén ENCENDIDAS

H.PWiz
fuente
1
Tenga en cuenta que en la puerta que tiene cada uno de los 4 ?s corresponde a uno de los 4 estados de A B.
Ad Hoc Garf Hunter
@HeebyJeebyMan Interesante, no lo había considerado. Acabo de encontrar esta puerta por suerte
H.PWiz
1

354 nodos, 428 bordes

Solo para demostrar que es posible. Mejoraré esto más tarde con algo de caché.

(con suerte no hay error de código)

Traté de escribir un programa de Mathematica aquí para verificar la validez del programa, pero probablemente no funcione porque hay demasiadas variables.

El resultado fue generado por un programa de computadora: ¡ Pruébelo en línea!


Yo uso una puerta que se ve así:


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

donde (#)están los indicadores 1, (a).. (f)son valores.

Luego,


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

Además, esta puerta


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

da


b = not a

. Use esos dos tipos de puertas para construir cualquier expresión.

Por supuesto, este es para afirmar que (a)debe ser cierto:


(a) ----- (#)
usuario202729
fuente
1

81 nodos, 108 bordes

Usando 13 nodos y 14 aristas, creamos la siguiente compuerta Adder (C (arry) = X AND Y, S (um) = X XOR Y):

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

Use cuatro sumadores M1, M2, M3, M4 para agregar A + B, C + D, E + F, G + H, respectivamente, con el acarreo resultante C1, C2, C3, C4 y la suma S1, S2, S3, S4.

Use dos sumadores M5, M6 para agregar S1 + S2, S3 + S4, con el resultado resultante C5, C6 y suma S5, S6.

Use un Adder M7 para agregar S5 + S6 para obtener C7 y S7.

Ahora conecte todos los transportes a un solo nodo indicador como el siguiente:

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

y obligar a S7 (el módulo 2 de la suma de 8 valores) a ser 0 por este circuito:

S7--1 -? - 1

Sostengo que este circuito obliga exactamente a que dos valores ABCDEFGHestén ENCENDIDOS, ya que solo puede ser un número par (ya que S7 es 0), y no puede haber más de 3 valores ENCENDIDOS (ya que solo uno de C1-C7 está ENCENDIDO).

justo
fuente